1
$\begingroup$

$ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $

I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My selected word : $ a ^ {m! + m} c ^ {m! + m} b ^ {m} b ^ {m} c ^ {m! + m} a ^ {m! + m} $ where the first $ b ^ {m} $ are the distinguished characters.

It seems to me that it isn't possible to pump this word in any way possible so it isn't contex-free langauge. Have I right?

$\endgroup$
2
$\begingroup$

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

Intuitively we cannot recognize $L$ using a pushdown automaton as the number of $b$'s has to be used twice, once in comparing against the number of $a$'s and once in comparing against the number of $c$'s. However, that is far from a proper proof.

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

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$. Let $s=uwy=uv^0wx^0y$, which 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. $s$ cannot be a palindrome.

  • $vwx$ contains only $b$s.
    Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}+1$. Then let $s=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.


Here are two related exercises.

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

Exercise 2. Show the following language is not context-free. (Hint, Ogden's lemma.) $$ L = \{w \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{a} \not= |w|_{c} \}\,. $$

$\endgroup$

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.