Example 7.6
Construct a pda that accepts the language generated by a grammar with
productions
We first transform the grammar into Greibach normal form, changing the
productions to
The corresponding automaton will have three states { 0 , q 1 , q 2 }, with initial state
q 0 and final state q 2 . First, the start symbol S is put on the stack by
The production S → aSA will be simulated in the pda by removing S from the
stack and replacing it with SA, while reading a from the input. Similarly, the rule
S → a should cause the pda to read an a while simply removing S. Thus, the two
productions are represented in the pda by
In an analogous manner, the other productions give
The appearance of the stack start symbol on top of the stack signals the
completion of the derivation and the pda is put into its final state by
The construction of this example can be adapted to other cases, leading toa
general result.
Construct a pda that accepts the language generated by a grammar with
productions
We first transform the grammar into Greibach normal form, changing the
productions to
The corresponding automaton will have three states { 0 , q 1 , q 2 }, with initial state
q 0 and final state q 2 . First, the start symbol S is put on the stack by
The production S → aSA will be simulated in the pda by removing S from the
stack and replacing it with SA, while reading a from the input. Similarly, the rule
S → a should cause the pda to read an a while simply removing S. Thus, the two
productions are represented in the pda by
In an analogous manner, the other productions give
The appearance of the stack start symbol on top of the stack signals the
completion of the derivation and the pda is put into its final state by
The construction of this example can be adapted to other cases, leading toa
general result.