Heres what I got but I am not sure if ive overlooked something or got anything wrong.

$L = \{a^kb^mca^nb^m : k < n \space \wedge \space k,m > 0\}$

Assume that $L$ is a CFL. Let $p$ be the pumping length given by the pumping lemma. We choose the string $s = a^{p-1}b^pca^pb^p$. We know by the pumping lemma that $s$ can be divided into the string $ s = > uvxyz$ where $uv^1xy^1z \in L$ for each $i \geq 0$, $|vy| < 0$, and $|vxy| \leq p$.

Consider the three cases:

  1. $vy$ contains a $c$: The string $uv^2xy^2z$ then has two $c$'s and thus is not in $L$.
  2. $vy$ contains atleast one $a$: We pump upwards to $uv^2xy^2z$ if $vy$ is on the left of the $c$. We pump downwards to $uv^0xy^0z$ if $vy$ is on the right side of the $c$. I both cases, $k \geq n$ and the string is thus not in $L$.
  3. $vy$ contains atleast one $b$: The string $uv^2xy^2z$ will make the substrings consinsting of only $b$'s not equals. Then the string cant be in $L$

Each case results in a contradiction. There for the pumping lemma does not hold and $L$ is not context free.


Your Answer

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

Browse other questions tagged or ask your own question.