2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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
    Commented Sep 12, 2017 at 19:28

1 Answer 1

Reset to default
2
$\begingroup$

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*} $$

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 12, 2017 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
    Commented Sep 12, 2017 at 20:35
  • $\begingroup$ My teacher always asks to make grammars without $\varepsilon$ productions, I think that's a good exercise. $\endgroup$
    – matheussilvapb
    Commented Sep 12, 2017 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.