Skip to main content
2 of 4
Fixed my snafu.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

We can just use the standard pumping lemma for context-free language.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

  • $vwx$ contains at least one letter other than $b$.
    Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Then $uwy$ is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $uwy$ cannot be a palindrome.

  • $vwx$ contains only $b$s.
    Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}-1$. Then $uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.


Exercise. Show the following language is not context-free. $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{b} \not= |w|_{c} \}\,. $$

John L.
  • 39.1k
  • 4
  • 34
  • 91