Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to prove that the language $L = \{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \}$ is not context-free by using Parikh's theorem.
My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be written as a subset of linear vectors. From this it follows that $\psi(L)$ is not semi-linear.
My problem is to show that by a formal proof.
If $L$ were context-free then, applying the homomorphism mapping both letters to $a$, also the following language would be context-free: $$ L' = \{ a^{2n^2+2n} : n \geq 0 \}. $$ According to Parikh's theorem, a unary language is context-free iff the corresponding subset of $\mathbb{N}$ is eventually periodic. Yet the sequence $2n^2+2n$ has arbitrarily long gaps, since $2(n+1)^2+2(n+1)-2n^2-2n = 4n+4$. Therefore the set $\{2n^2+2n : n \geq 0\}$ is not eventually periodic, and so $L'$ is not regular or context-free.
