I need to bulid a context-free grammar for

$\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$

Not palindrom at all: We will say that a word $w$ is not palindrome at all if for all $i$ such that $1\leq i\leq |w|$ the $i$ letter from the beginning of $w$ is not the same like the $i$ letter of $w$ from the end, for example $abbacb\in \mathscr{L_4}$ but $ca\color{gray}bba\color{gray}bcb\notin\mathscr{L_4}$, the word must contain a even number of digits, because if there were an odd number of digits, so the middle digit "equals to itself".

My attempt: Let's denote $S_{\text{pal}}$ from palindrome grammar and $S_{\neg\text{pal}}$ for the not palindrome at all grammar

$$\\S_{\neg\text{pal}}\to a S_{\neg\text{pal}}b\big|bS_{\neg\text{pal}}a\big|aS_{\neg\text{pal}}c\big|cS_{\neg\text{pal}}a\big|cS_{\neg\text{pal}}b\big|cS_{\neg\text{pal}}b\big|\epsilon$$

Similar question here. I'm not sure if my attempt is correct or not

  • 2
    $\begingroup$ Do you have a specific question about your attempt? We don't appreciate "please check my homework"-type questions. Have you tried proving your grammar correct? $\endgroup$
    – Raphael
    Dec 29, 2015 at 14:41

2 Answers 2


Your attempt looks correct to me

$$\\S_{\neg\text{pal}}\to \color{red}a S_{\neg\text{pal}}\color{blue}b\big|\color{blue}bS_{\neg\text{pal}}\color{red}a\big|\color{red}aS_{\neg\text{pal}}\color{green}c\big|\color{green}cS_{\neg\text{pal}}\color{red}a\big|\color{blue}bS_{\neg\text{pal}}\color{green}c\big|\color{green}cS_{\neg\text{pal}}\color{blue}b\big|\varepsilon$$

Let us say that for a word of length $n$ such that $n\in\mathbb{N}$ is even for each letter in the $i$ from the begining $1\leq i\leq n$ you ensure that in the place $i$ from the end you have a diffrent letter

for example: $\color{red}a\color{blue}b\color{green}c\color{blue}b\color{red}a\color{blue}b\in \mathscr{L_4}$

  • $\begingroup$ We prefer detailed answers that come with reasons, evidence, proof, or other form of justification. $\endgroup$
    – D.W.
    Dec 30, 2015 at 20:38
  • $\begingroup$ I don't find the justification/argument convincing. It contains a claim that there is a different letter (which is merely a restatement of what needs to be proven), but where is the justification for this claim? There is no proof and no attempt at an argument for why this will necessarily be so. The techniques here would be one way to provide a more convincing argument. $\endgroup$
    – D.W.
    Dec 30, 2015 at 22:04
  • $\begingroup$ It would be difficult to provide a convincing argument that the answer is correct as the grammar does not generate $bc$ and my understanding is that that string should be generated. (The root cause is probably a typo, though), $\endgroup$ Dec 31, 2015 at 11:38

Just use something like:

$ S \rightarrow a S b \mid a S c \mid b S a \mid b S c \mid c S a \mid c S b \mid a b \mid a c \mid b a \mid b c \mid c a \mid c b $

This ensures the $i$-th symbol from the beginning is different from the $i$-th from the end.

  • 2
    $\begingroup$ Without $|\epsilon$? (+1) $\endgroup$
    – user44244
    Dec 29, 2015 at 14:05
  • 4
    $\begingroup$ Wasn't the grammar in the question OK? $\endgroup$ Dec 29, 2015 at 14:30

Your Answer

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