$**$ Solve all but submit $5$ only.

Q$1.$ Prove using pumping theorem for regular languages that $L=\{a^n{b}^m,m2n\}$ is not regular.

Q$2.$ Prove by induction that for the following CFG G$,L(G)=\{win\{a,b{\}}^{**},n_a(w)=n_b(w)\}.$

$S$ SASBS $|$ SBSAS $|$

$AaBb$

Q$3.$ Find a rightmost derivation and a leftmost derivation for the string aabbbb using the grammar

$S{}_{A\text{A}\text{B}\text{C}},BSb|,CCSb|b$

Draw the parsing tree of each derivation.

Q$4.$ Find an s$-$grammar for each of the following languages:

$a-L=\{a^n{b}^{n+1}$:$n2\}$

$b-L=\{a^n{b}^m$:$n1,m=3n+1\}$

Q$5.$ Show that the following grammar $G$ is ambiguous

$S$aSbS$|aS|$

$($Consider the string aab. Show that it has two:

a$)$ Parse trees.

b$)$ Leftmost derivations.

Q$6.($Grammar Simplification$)$ Begin with the grammar:

$SCSBb|aC|AD$

$A$aAS$|aCA$

$BC|bb|ACD$

$CAC|cC|$

$DDA|a|b$

a$)$ Remove $-$productions.

b$)$ Remove any unit$-$productions in the resulting grammar.

c$)$ Remove any useless symbols in the resulting grammar.

d$)$ Put the resulting grammar into Chomsky Normal Form.

Q$7.$ Prove using pumping theorem for CFL that $L=\{a^n{b}^n{c}^m,n0,(m)>2n\}$ is not context free.

Q$8.$ Design an NPDA for the language $L=\{win\{a,b{\}}^{+},n_a(w)2n_b(w)\}.$

Q$9.$ Design a DPDA that accepts the following language and trace its configuration changes given the input

aaabb$: $($$ is a marker for the end of input$)$

$L=\{a^n{b}^m$$$,m2n\}$

Q$10.$ Give an NPDA corresponding to the following CFG $($Use the construction given in class$)$:

$S$aSBb$|aC|bA$

$A$aAS$|bA|a$

$BbB|aAC$

$CcC|$