Pumping Lemma: context free squared number proof

359 Views Asked by At

I'm just doing a Pumping Lemma proof for showing a language is not Context Free by contradiction and would just like to know if it's valid. Note that for reasons, I'm only allowing $i = 0$ in the last part.

$L = \{ a^{n^{2}} \mid n \text{ is more than $0$}\}$

Assume $L$ is context free. So the Pumping Lemma applies, and so for any string $w \in L$ with $|w|\geqslant n$ there exist strings $x, y, z, u, v$ such that $w = xyzuv$ and

i. $|yzu| \leqslant n$

ii. $|y| + |u| > 0$

iii. $xy^i zu^iv \in L$ for all $i \geqslant 0$

Let $w = a^{n^{2}}$. So $w \in L$ and $|w| \geqslant n$, and $w = xyzuv$, $|yzu| ≤ n$, $|y|+|u| > 0$ and $xy^i zu^i v \in L$ for all $i \geqslant 0$. Now as $|yzu| \leqslant n$, this means $|yzu| = |y| + |z| + |u| \leqslant n$ and so $|y| + |u| \leqslant n$.

Let $i = 0$ and consider $|xy^0 zu^0 v| = |xzv| = |xy^1zu^1v| −|y| − |u| = n^2 − (|y| + |u|) \geqslant n^2 − n \geqslant (n − 1)^2$. So $n^2 = |xy^1zu^1w| > |xy^0 zu^0 v| > (n − 1)^2$ , and so $xy^0 zu^0v \notin L$. This is a contradiction, and so $L$ is not context-free.