# Is Language $L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b}$ and $|w|_{b} \not\equiv |w|_{c} \}$ context free?

$$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?

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} \}\,.$$