Any string of a context-free language has a leftmost derivation. We set up
the NPDA so that the stack contents “corresponds” to this sentential form:
every move of the NPDA represents one derivation step.
The sentential form is
(The char ac ters already read) + (sym bols on the stack)
– (Final z (ini tial stack sym bol)
In the NPDA, we will construct, the states that are not of much
importance. All the real work is done on the stack. We will use only the
following three states, irrespective of the complexity of the grammar.
(i) start state q 0 just gets things initialized. We use the transition from
q 0 to q 1 to put the grammar’s start symbol on the stack.
δ
λ
( , , ) {( , )}
q
Z
q Sz
0
1
→
(ii) State q 1 does the bulk of the work. We represent every derivation
step as a move from q 1 to q 1 .
(iii) We use the transition from q 1 to q f to accept the string
δ
λ
( , , ) {( , )}
q
z
q z
f
1
→
Example Consider the grammar G
S A B a b S P
= ({ , , }, { , }, , ), where
P
S
a S
aAB A aA A a B
bB B
b
= →
→
→
→
→
→
{
,
,
,
,
,
}
These productions can be turned into transition functions by rearranging
the components.
Thus we obtain the following table:
(Start)
δ
λ
( , , ) {( , )}
q
z
q Sz
0
1
→
S
a
→
δ
λ
( , , ) {( , )}
q a S
q
1
1
→
S
aAB
→
δ( , , ) {( ,
)}
q a S
q AB
1
1
→
A aA
→
δ( , , ) {( , )}
q a A
q A
1
1
→
A a
→
δ
λ
( , , ) {( , )}
q a A
q
1
1
→
B
bB
→
δ( , , ) {( , )}
q b B
q B
1
1
→
B
b
→
δ
λ
( , , ) {( , )}
q b B
q
1
1
→
(fin ish)
δ
λ
( , , ) {( , )}
q
z
q z
f
1
→
168
Theory of Automata, Formal Languages and Computation
S
a AB
δ q,a,S
() 1
{(,
)}
qAB 1