132(4CONTEXT-FREE LANGUAGES(We assume that the PDA starts with a special symbol $ in the
stack, i.e., the initial configuration is (s, X, $).)
The PDA accepts an input string as long as it reaches a final state
after it finishes reading the input symbols (regardless of whether
the stack is empty or not); that is, the PDA accepts a string x E C*
if (s, X, E) C (q, &, 7) for some q E F and some y E Iā*.- APDAM=(Q,C,r,S, s, F) is a deterministic PDA if no configuration
of M has more than one successor configuration (but a nonfinal config-
uration may have no successor). For each of Examples 3.28-3.33, do the
following:
(a) Determine whether the PDA given in the example is deterministic
or not.
(b) If the answer to (a) is no, then determine whether there is an
equivalent deterministic PDA accepting the same language. If
yes, present your deterministic PDA; if no, show why not. [Hint:
One way of eliminating (part of) nondeterminism in a PDA is to
use the PDA model of Exercise 3(c) .]
3.5 Pushdown Automata and Context-Free Grammars
Many ideas in the design of pushdown automata used in the last section are
similar to those used in the design of context-free grammars. This observa-
tion suggests a close relation between these two language processors. Indeed,
we prove in this section that the class of languages accepted by pushdown
automata is exactly the class of context-free languages.
Theorem 3.35 For every context-free grammar G, there is a PDA M such
that L(M) = L(G).Proof. Given a context-free grammar G = (V, C, R, S), we will construct a
PDA M to simulate grammar G such that L(M) = L(G). The idea of the
PDA is simple: On input X, we first push the start symbol S of grammar G
into the stack. Then, we simulate the leftmost derivation of ix: by G. At each
step, if the top symbol of the stack is a nonterminal A, then we select a rule
A + ul of G and replace A by ul. If the top symbol is a terminal symbol a,
then we try to match it with the next input symbol. If they do not match,
then this computation path rejects; otherwise, we remove this symbol from
the stack and continue. Note that each terminal symbol at the top of the
stack belongs to the string generated in this derivation. Thus, if all those
symbols match correctly with those of the input, then the input is generated
by G and we accept it.
The only technical problem with the above idea is that the right-hand side
UJ of a rule A + UI may have more than one symbol, but our PDA can only
push into the stack one symbol at a time. This problem can be easily resolved