# Is the language of all non-palindromes context-free?

Is the language $L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}$, context-free? I think this grammar:

$S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\ A \rightarrow aAa \mid bAb \mid aAb \mid bAa \mid a \mid b \mid aa \mid ab \mid ba \mid bb$

generates it, but I'm unable to conclude anything using the pumping lemma for context free languages.

• I don't understand the "but" here. If you have a grammar, prove it correct and done. Why would you be surprised that the Pumping lemma proof doesn't work if you think the language is context-free?
– Raphael
Sep 12 '17 at 19:28

If $w$ is not a palindrome then there must be some $i$ such that the $i$th letter from the left is different from the $i$th letter form the right; and vice versa (prove!). This means that $$L = \{ \Sigma^{i-1} a \Sigma^* b \Sigma^{i-1} : i \geq 1 \} \cup \{ \Sigma^{i-1} b \Sigma^* a \Sigma^{i-1} : i \geq 1 \},$$ which is easily seen to be context-free.

Your grammar almost manages to capture this characterization. Unfortunately, it doesn't generate the words $ab$ and $ba$. A simpler grammar is \begin{align*} &S \to aSa|bSb|aTb|bTa \\ &T \to aT|bT|\epsilon \end{align*}

• Thanks, your grammar is way simpler than mine, but I think the idea is the same. Actually your grammar is a type-0 grammar due to that $\varepsilon$-transition, I wonder if you can make it without that. Sep 12 '17 at 19:49
• My grammar is context-free (some people disallow $\epsilon$ transitions so that a CFG would automatically be a CSG, but that's not the only choice possible). It is, however, extremely simple to get rid of the $\epsilon$ production. The resulting grammar is $S\to aSa|bSb|aTb|bTa|ab|ba$, $T\to aT|bT|a|b$. Sep 12 '17 at 20:35
• My teacher always asks to make grammars without $\varepsilon$ productions, I think that's a good exercise. Sep 12 '17 at 20:55