0
$\begingroup$

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.

$\endgroup$

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.