1
$\begingroup$

I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and $x$, you clearly get out of language when you pump up. If you do the same with $b$'s and pump down, you get out of language as well. But how dow do you show situation where there are only $a$'s in $v$ and just $b$'s in $x$?

Thank you

$\endgroup$
1
  • $\begingroup$ Pump down. For large enough $n$ (in terms of the pumping length), you well reach a contradiction. $\endgroup$ – Yuval Filmus May 23 '20 at 7:49
1
$\begingroup$

Suppose towards a contradiction that $L$ is context-free and let $c$ be the pumping length of $L$. Consider the word $a^{c^2} b^c$ which, by the pumping lemma, can be written as $uvwxy$ with $1 \le |vx| \le c$.

Notice that:

  • $vx$ cannot contain only $b$s, since otherwise $uwy \not\in L$.
  • $vx$ cannot contain only $a$s, since otherwise $uv^2wx^2y \not\in L$.
  • none of $v$ and $x$ contains both $a$s and $b$s, since otherwise $uv^2wx^2y \not\in L$.

We conclude that $v$ contains only $a$s, $x$ contains only $b$s, and $x$ contains at least one $b$. Then, by the pumping lemma, $a^{c^2-|v|} b^{c-|x|} = uwy \in L$. This is a contradiction since: $$ (c - |x|)^2 \le (c - 1)^2 = c^2 - 2c + 1 \le i^2 - c < i^2 - |v|. $$

$\endgroup$
1
  • $\begingroup$ Thank you very much! This is exactly what I was looking for :-). Could not get the last part properly together. Thank you once again and have a nice day! $\endgroup$ – Mike May 24 '20 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.