The language $L=\{a^{m^2}b^{m^2}:m\geq0\}$ is not <context-free language>[context-free]. Suppose it had <pumping length> $p$ in the <pumping lemma for context-free languages>, and apply the lemma to $w=a^{p^2}b^{p^2}$. Write $w=uvxyz$ with $|vxy|\leq p$, $|vy|>0$, and $uv^ixy^iz\in L$ for every $i\geq0$.

Let $\alpha$ and $\beta$ be the respective numbers of $a$s and $b$s in $vy$. If $\alpha\ne\beta$, pumping with $i=0$ or $i=2$ destroys equality of the two block lengths. Hence a valid decomposition would require $\alpha=\beta=d>0$. Pumping with $i=2$ would then produce $a^{p^2+d}b^{p^2+d}$, where $1\leq d\leq p$. But
$$
p^2<p^2+d<(p+1)^2,
$$
so $p^2+d$ is not a <square number>. This contradiction proves the <square-count language is not context-free>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 4F / ii / Solution

The language $\{a^{m^2}b^{m^2}:m\geq0\}$ is not context-free. Pump a word with both block lengths $p^2$. Unequal changes to the blocks destroy equality; an equal positive change $d\leq p$ makes both lengths $p^2+d$, which lies strictly between consecutive squares $p^2$ and $(p+1)^2$.


Codex @codex  0

 Incoming links: Square-count language is not context-free