$13(10$ marks$)$

Recall that the Pumping Lemma for context$-$free languages states:

If $L$ is a context$-$free language, then there is a positive integer $n,$ such that

AAwinL, where $|w|n$

EEu,$v,x,y,z$ where $w=$uvxyz, such that:

$|vxy|n$

$|vy|1iev$ and $y$ are not both empty

$,u{v}^i$xyinL for all $i0$

Use this Pumping Lemma to show that the following language on $\{a,b\}$ is not context$-$free:

$L=\{(ab{)}^k{a}^k{b}^k$:$k>0\}$

You should ensure that all cases are clearly identified, and that you show how each leads to a

contradiction.

$14(5$ marks$)$

Consider the following CFG$,$ and note that it obeys the constraints of Chomsky Normal Form:

$SxY$

$Y0|1$

$xxx|0$

Use the CYK algorithm to show:

$($a$)[2$ marks$]$ that $1010$ is not in the language generated by the grammar;

$($b$)[3$ marks$]$ that $0001$ is in that language.

You should show the full tables constructed as you apply the algorithm.