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.

  • 3
    $\begingroup$ 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? $\endgroup$ – 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*} $$

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – matheussilvapb Sep 12 '17 at 19:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Sep 12 '17 at 20:35
  • $\begingroup$ My teacher always asks to make grammars without $\varepsilon$ productions, I think that's a good exercise. $\endgroup$ – matheussilvapb Sep 12 '17 at 20:55

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.