Chapter 7: Pushdown Automata ~ 257
RIO : S(qll' A, B) = (q", as)
R 1 ]
S(q". A, B) = (q", b)
R 12
Seq, $. 20) = (q, A)
Here R 1 changes the initial ill (p, 11', Z) into (q, 11', SZ). R 2 and R 4 are for
remembering the next symbol. R 6 -R ll are simulating the productions. R 3 and R s
are for matching the cunent input symbol and the topmost symbol on PDS and
for erasing it (in PDS). Finally. R 12 is a move for erasing Z and making the
PDS empty when the last symbol $ of the input string is read.
To get a leftmost derivation for an input string lV, apply the unique
transition given by R J to R 12 • When we apply R 6 to R]J, we are using a
cOlTesponding production. By recording these productions we can test whether
]V E L(G) and get a leftmost derivation. The parsing for the input string
abbbab is given m Table 7.4.
The last column of Table 7.4 gives us a leftmost derivation of abbbab. It
is S =} aAB =} abSB =} abbBAB =} abbbAB =} abbbaB =} abbbab.
TABLE 7.4 Top-down Parsing for w of Example 7.13
Step
State
Unread input
Pushdown stack
Transition
Production
used
applied
1
p
abbbabS
Zo
2
q
abbbabS
SZo
R 1
3
qa
bbbabS
SZo
R 2
4
qa
bbbabS
aABZ o
R 6
S ---7 aAB
5
q
bbbabS
ABZ o
R 3
6
qb
bbabS
ABZ o
R 4
7
qo
bbabS
bSBZ o
Rg
A ---7 bS
8
q
bbabS
SBZ o
R s
9
qb
babS
SBZ o
R 4
10
qb
babS
bBABZ o
R7
S ---7 bBA
11
q
babS
BABZ o
R s
12
qb
ab$
BABZ o
R 4
13
qb
abS
bABZ o
R 11
B ---7 b
14
q
abS
ABZ o
R s
15
qa
b$
ABZ o
R 2
16
qa
b$
aBZ o
Rg
A---7a
17
q
b$
BZ o
R 3
18
qb
S
BZ o
R 4
19
qD
$
bZ o
R 1i
B ---7 b
q
S
Zo
R s
21
q
A
A
R 12