Question $1$

$[15]$

Build a DPDA to show that the language $L=\{(ba{)}^{n}a(ab{)}^{n-2}|n>2\}$ is deterministic context free.

Question $2$

$[15]$

Prove that the language $L=\{b{a}^n{b}^{2n}{a}^{n+1}|n>0\}$ over the alphabet ${\displaystyle \underset{?}{\overset{?}{}}}=\{a,b\}$ is non$-$context free. Use the pumping lemma with length.

Question $3$

$[10]$

Let $L_1$ be the grammar generating $(aa{)}^{**}.$ Let $L_2$ be the grammar generating $(a+b{)}^{**}ba(a+b{)}^{**}.$ First provide the grammars generating $L_1$ and $L_2$ respectively. Then apply the applicable theorem of Chapter $17$ to determine $L_1{L}_2.$

Question $4$

$[10]$

Decide whether the grammar given below generates any words.

$SxY$

$xSY$

$YSx$

$xa$

$Yb$