Question

4. Show that the pda constructed in Example 7.6 accepts the strings aabb and aaabbbb, and that both strings are in the language generated by the given grammar. 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 A bB, The corresponding automaton will have three states (go, 91,92), with initial state go and final state q2. First, the start symbol S is put on the stack by 6 (go, A, 2) (gi, S2)). 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 δ (qi, a,S) = {(a, SA), (q, λ)) 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 to a general result.

Answer 1

a abb CaD Ne a/aa 又 ,-s tちe initiaf

aa a,a) A cupに hins (92,00) 少 aa) uia า (qs, e, z) @pz) →