Chapter 7: Pushdown Automata };l, 249
Define G = (V", {a, b}, P. S). where V" consists of
[qo, 20, qo]. [q1' Zo, qo]· [qo, a, qa], [q), a, qo]
[qo· Zo, q1]' [q), Zo, qI1. [qo· a, qd, [qj, a, qd
The productions in P are constructed as follows:
The S-productions are
PI: 5 -+ [qo, Zo, qa],
8(qo, a. Zo) = {(qo, aZo)} induces
P 3 : [qo, Zo, qo] -+ a[qo, a, qo][qo. Zo, qo]
P 4 : [qo, Zo, qo] -+ a[q(j, a. q1][q1, Zo, qo]
P 5 : [qo· Zo, q!l -+ a[qo, a. qo] [qo, Zoo q1J
P 6 : [qo, Zo, qj] -+ a[qo, a. ql][q], Zoo ql]
8(qo, a. a) = {(qo. aa)} yields
P 7 : [qo, a, qo] -+ a [c/o. a. qo][qo, a, qo]
Pg: [qo. a, qoJ -+ a[qo, a. q1][qj, a, qo]
P 9 : [qo, a. ql] -+ a[qo· a, qo][qo, a. qd
P IO : [qo· a, ql] -+ a[qo, a, q!l[ql, a, q!l
PlJ: [qo, a. qo] -+ b[ql' a. qo]
PI:: [qo· a, qd -+ b[({r, a, q1J
b(qj. b, a) = {(qj, a)} yields
p . [qj. a, qoJ -+ b[qj. a, qaJ
. 13'
P j4 : [q1, a, qd -+ b[qr, a, qd
8(q], a. 0) = {(qj. A)} gIves
P j5 : [qj, a, qd -+ a
8(q;, A. Zo) = {(ql, A)} yields
P 16 : [qj, Zo· ql] -+ A
Note: When the number of states is a large number, it is neither necessary
nor advisable to write all the productions. We construct productions involving
those variables appearing in some sentential form. Using the constructions in
Chapter 6, vve can simplify the grammar further.
Theorem 7.5 Tne intersection of a context-free language L and a regular
language R is a context-free language.