1. Let S->aB|bA,A->aS|bAA|a,B->bS|aBB|b. Derive the string aaabbabbba as left most derivation.

2. Construct a PDA accepting {anb2n; n>=1} by final state.

3. Construct PDA for the grammar
S->aB|bA,A->a|aS|bAA
B->b|bS|aBB
B->b|bS|aBB
Check for the validation of string ab.

4. Give the parse tree construction of 1001 ad +*-xyxy for the given grammars.
1)S->A|B
A->0A|^
B->0B|1B|^
Parse tree for 1001

5. Construct aPDA for the given grammar and check for the validation of abcba and acb.
S->aSa|bSb|c
6. Show that the grammar S->a|Sa|bSS|SSb|SbS is ambiguous

7. Construct a PDA for the given grammar and check for the validation of aa*a0 and (a0+a).
E->I|E+E|E*E|(E),I->a|Ia|0|I0

7 Find a derivation tree of a*b+a*b given that a*b+a*b is in L(G) where g is given by
S->S+S|S*S, S->a/b

8) Show that the grammar S->a/abSb/aAb, A->bS/aAAb is ambiguous . (6marks)

9) Consider the following productions
S->aB|bA
A->aS|bAA|a
B->bS|aBB|b
for the string aaabbabbba find a leftmost derivation.

10) Construct a PDA accepting by empty stack the language {ambncn/m,n>=1}

11)Convert the PDA P=({p,q},{0,1},{x,z0}, δ,q,z0) where:

1. δ(q,1,z0)={(q,xz0)}
2. δ(q,ε,z0)={(q,ε)}
3. δ(q,1,x)={(q,xX)}
4. δ(q,0,x)={(p,x)}
5. δ(q,ε,x)=(q,ε)
6. δ(p,1,x)=(p,ε)
7. δ(p,0,z0¬)=(q,z0)
12) Convert the PDA P=({p,q},{0,1},{x,z0}, δ,q,z0) where:
1. δ[q 0 z0]={(q,x,z0)}
2. δ[q 0 x]={(q,x,x)}
3. δ[q 1 x]={(q,x)}
4. δ[q ε z0]={(q,ε)}
5. δ[p ε x]={(p,ε)}
6. δ[p 1 x]={(p,x,x)}
7. δ[p 1 z0]={(p,ε)}
Soln:
1. δ[q 0 z0]={(q,x,z0)}
At q: [q z0 q]->0[q x q][q z0q]
[q z0 q]->0[p x p][p z0q]
At p: [q z0 p]->0[q x q][q z0 p]
[q z0 p]->0[q x p][p z0 p]
2. δ[q 0 x]={(q,x,x)}
At q: [q x q]->0[q x q][q x q]
[q x q]->0[q x p][p x q]
At p: [q x p]->0[q x q][q x p]
[q x p]->0[q x p][p x p]
3. δ[q 1 x]={(q,x)}
At q:[q x q]->1[q x q]
At p:[q x p]->1[q x p]
4. δ[q ε z0]={(q,ε)}
[q x q]->ε
5. δ[p ε x]={(p,ε)}
[p x p]->ε
6. δ[p 1 x]={(p,x,x)}
At q: [p x q]->1[p x q][q xq]
[p x q]->1[p x p][p xq]
At p: [p x p]->1[p x q][q xp]
[p x p]->1[p x p][p xp]
7. [p 1 z0]={(p,ε)}
[p z0 p]->1