122 CONTEXT-FREE LANGUAGES
3.4 Pushdown Automata
Context-free grammars are generators for context-free languages, from which
we can obtain sentences in the language by repeatedly applying the grammar
rules. Using a context-free grammar to parse a given string is, though possible,
not easy. In this section, we introduce a model of recognixers, called pushdown
automata, to recognize strings in a given context-free language.
A pushdown automaton (PDA) is a nondeterministic finite automaton
equipped with an additional storage device called a stuck, and a stack head
which reads from and writes to the top of the stack (see Figure 3.10). The
stack is a first-in last-out storage device with no predetermined size limit. The
stack head always scans the top element of the stack. It performs two basic
stack operations: push (add a new symbol at the top of the stack) and pop
(read and remove the top symbol from the stack).
More formally, we define a PDA as a 6-tuple M = (Q, C, IY, S, s, F), where
Q, C, s and F are the same as those in an NFA, I? is a finite alphabet of stack
symbols, and S is a transition function
6 : Q x (IX u {E}) x (I’u {E}) + 2QX(rU(E)).For q E Q, a E C and u E I’, an instruction (p, V) E S(q, a, u) means that if the
PDA M is in state q, reading a tape symbol a and a stack symbol u, then one
of its possible moves is to replace the top symbol u of the stack by V, move
the tape head one cell to the right and then move into state p. It is possible
that u or v is equal to E. When v = E, that is, (p, E) E S(q, a, u), it means that
the PDA M may simply delete the top symbol u of the stack without writing
a new symbol to the stack (this is a simple pop operation). When u = E,
that is, (p, v) E S(q, a, E), it means that the PDA M performs this operation
without reading what the top symbol of the stack is (this is a simple push
operation). It is also allowed to have a = E, that is, (p, v) E S(q, E, u). This
type of instructions is like the E-move of an NFA; that is, the PDA M performs
tape
‘5
Figure 3.10: A pushdown automaton.