is replaced by
Since δ can have only a finite number of elements and each can only add a
finite amount of information to the stack, this construction can be carried
out for any pda.
Section 7.2
3. You can follow the construction of Theorem 7.1 or you can notice that the
language is {a n + 2 b 2n+1 : n > 0}. With the latter observation we get a solution
where q 0 is the initial state and q f is the final state.
4. First convert the grammar into Greibach normal form, giving S → aSSS; S →
aB; B → b. Then follow the construction of Theorem 7.1.
free grammar. From that grammar we can then construct an equivalent threestate npda, using Theorem 7.1. Because of the transitivity of equivalence, the
original and the final npda's are also equivalent.
9. We first obtain a grammar in Greibach normal form for L, for example, S →
aSB|b, B → b. Next, we apply the construction in Theorem 7.1 to get an npda
Since δ can have only a finite number of elements and each can only add a
finite amount of information to the stack, this construction can be carried
out for any pda.
Section 7.2
3. You can follow the construction of Theorem 7.1 or you can notice that the
language is {a n + 2 b 2n+1 : n > 0}. With the latter observation we get a solution
where q 0 is the initial state and q f is the final state.
4. First convert the grammar into Greibach normal form, giving S → aSSS; S →
aB; B → b. Then follow the construction of Theorem 7.1.
free grammar. From that grammar we can then construct an equivalent threestate npda, using Theorem 7.1. Because of the transitivity of equivalence, the
original and the final npda's are also equivalent.
9. We first obtain a grammar in Greibach normal form for L, for example, S →
aSB|b, B → b. Next, we apply the construction in Theorem 7.1 to get an npda