3.4 Pushdown Automata 123
the operation as in the case of (p, V) E s(4, a, u), except that it does not read
a tape symbol (and so its tape head does not move).
At the beginning, a PDA M = (Q, C, I?, s, F, 6) is in state s, having an
empty stack, and its tape head is scanning the leftmost symbol of the input
tape. At the end, we say a PDA accepts the input if, in one of its computation
paths, it reads all input symbols, has an empty stack, and reaches a final state
q E F. We let L(M) be th e set of all strings accepted by M.
Example 3.28 Consider the PDA M = ({q,p}, {a, b, c}, {a, b}, 6, q, {p}),
where S is defined as follows:Determine what L(M) is.
Solution. This machine works in the following way: At the initial state q, it
pushs the input symbols a and b to the stack until it reads a tape symbol
c. After reading c, it moves to state p. In state p, M compares each symbol
on the tape with the top symbol of the stack. If they are all equal, then the
machine accepts the input.
Let w E {a, b) be the prefix of the input before the first occurrence of
symbol c, and IX: be the suffix of the input after the first occurrence of c. We
note that, at the time of PDA M moving to state p, the string w is stored
in the stack in the reverse order (the first symbol of w is at the bottom of
the stack, and the last symbol of w is at the top). So, when it compares the
suffix z with the stack symbols, it compares the first symbol of x with the
last symbol of w, and so on. Therefore, it accepts only if z = wR. That is,
L(M) = {wcwR 1 w E {a,b}}. cl
To better understand how a pushdown automaton works, we need to define
the concept of configurations of a PDA. A configuration of a PDA M is a
record of information of M at a certain stage of computation, including the
state it is in, the tape symbols which it has yet to read, and the stack symbols
in the stack. That is, a configuration of a PDA M = (Q, C,Iā,S, s, F) is a
member in Q x C x Iā. A configuration (q,x,y) denotes that the PDA M
is in state q, its tape symbols to be read are X, with the tape head scanning
the leftmost symbol of X, and the stack currently holds symbols y (with the
leftmost symbol of y representing the top symbol of the stack).
For any two configurations (q, X, p> and (p, y, 7)) we say (p, y, 7) is a suc-
cessor configuration of (q, x, p) , and write (q, x,p) I- (p, y,y), if there is an
instruction (p, V) E S(q, a, u) such that x = ay and ,8 = ucll, y = zlctr for some
o! E I?*, where a, u, v may be equal to E. We write (q, x, ,8) p (p, y, r> if there
exists a sequence of configurations Co, (71,... , Cn such that Co = (q, x, p>,