Question $3$

Pumping Lemma

The pumping lemma with length for context$-$free languages $($CFLs$)$ can be stated as

follows: Let $L$ be a CFL generated by a CFG in CNF with p live productions.

Then any word win $L$ with length $>2^P$ can be broken into five parts:

$w=$uvxyz such that

length $(vxy)2^P$

length $(x)>0$

length $(v)+$ length $(y)>0$

and such that all the words $u{v}^{n}x{y}^{n}z$ with $nE\{2,3,4,$dots$\}$ are also in the language

L$.$ Use the pumping lemma with length to prove that the language

$L=\{(a{)}^n(b{)}^{3n}(a{)}^n|n>0\}$

over the alphabet ${\displaystyle \underset{?}{\overset{?}{}}}=\{a,b\}.$

Choose an appropriate word to pump. $(1$ mark$)$

Identify cases $-$ should be $5,2$ with $3$ subcases each. This makes essentially $9$ cases that

need to be argued cannot work. $(0\mathrm{.}5$ mark each case or subcase and $0\mathrm{.}5$ marks for saying

why it cannotbe pumped $-$ This gives $9$ marks in total$)$

Argue for contradiction. $(2$ marks$)$