0
$\begingroup$

I'm having a trouble proving it to be non-context-free.

For example, if I take w = $a^k b^k b^{k+1} a^{k+1}$, it would be problematic if the partition of $vxy$ with $|v| = |y|$ was in the $ b^{k+1} a^{k+1} $ part as I can't get it to be equal with $k$ or make the amount of $a$s and $b$s different.

We are also allowed to use Ogden's Lemma.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are you familiar with the pumping lemma proof that $\{a^nb^m \mid n \neq m\}$ isn't regular? $\endgroup$
    – Yuval Filmus
    Commented May 8, 2021 at 13:08
  • $\begingroup$ The trick is explained here: Prove that the following language is not regular: $\{ 0^i1^j \mid i\neq j \}$. $\endgroup$
    – Hendrik Jan
    Commented May 8, 2021 at 15:36
  • $\begingroup$ Consider $ab b^{p!+1} a^{p!+1}$. If $n,m$ can be zero, we can also consider $b^{p!} a^{p!}$. Here $p$ is a pumping length. $\endgroup$
    – John L.
    Commented May 8, 2021 at 21:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.