Unit 4

PUSH DOWN AUTOMATA AND POST MACHINES

1. Construct transition graph for PDA for L= {anbn |n≥1}.
2. Let L ={w|w over(a+b)*  and w contains atleast two occurrences of b. Construct PDA for L.
3. Construct PDA language for language of strings over (a+b)* having atleast one occurrence of substring ‘aa’.
4. Construct PDA language for odd palindromes over

∑ = {a, b} L = {a, b, aaa, bbb, aba, bab....}.

5.     Explain non deterministic pushdown automata in detail.

6.     State and explain for every context free grammar G, there is a push down automaton such that L{G} =L{M}.

7.     Construct a DPDA accepting balanced strings of brackets.

8.     Construct PDA for L= {w|w with start with a and end character ‘b’}.

9.     Construct PDA (NPDA) from CFG indicating the steps used in construction.

10. With help of PDA show that CFL are closed under union, concatenation and Kleen’s closure.