240 ~ Theory of Computer Science
for some q E F and ex E P'. But (qo. w, ZoZ~)) ~ (q, A, exZ'o) can be
obtained only by the application of R 2 • So the moves involved are those
induced by the moves of A. As Z'o is not a pushdown symbol in A, Z'o lying
at the bottom is not affected by these moves. Hence
(c/o, Aw, Z~)) rt (q. A. ex), q E F
So w E T(A) and N(B) ~ T(A). Thus,
L = N(B) = T(A)
EXAMPLE 7.6
Construct a pda A accepting the set of all strings over {a, b} with equal
number of a's and b·s.
Solution
Let
A =({q), [a. b]. [Zo, a, b], D, q, Zo, 0)
where Dis defined by the following rules:
D(q, a, Zo) = {(q, aZo)} D(q. b, Zo) = {(q, bZ o )}
D(q, a. a) = {(q. aa)} D(q, b. b) = {(q, bb)}
D(q. a. b) = {(q. A)} D(q. b, a) = {(q. A)}
D(q. A, Zo) = {(q, A)}
The construction of Dis similar to that of the pda given in Example 7.2.
But here we want to match the number of occurrences of a and b: so, the
construction is simpler. We start by storing a symbol of the input string and
continue storing until the other symbol occurs. If the topmost symbol in PDS
is a and the current input symbol is b. a in PDS is erased. If lV has equal
number of a's and b's, then (q. w. Zo) ~ (q, A, Zo) 1- (q, A, A). So
WE N(A). We can show that N(A) is the given set of strings over {a. b} using
the construction of 0.
7.3 PUSHDOWN AUTOMATA AND CONTEXT-FREE
LANGUAGES
In this section we prove that the sets accepted by pda (by null store or final
state) are precisely the context-free languages.
Theorem 7.3 If L is a context-free language, then we can construct a pda
A accepting L by empty store, i.e. L = N(A).