Let: $ G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0 $

I need to find the language (no need to formally prove). I have written many words but cannot seem to find a rule. After trying that path I rewrote the grammar in a shorter rules:

$$ S \to 0S0|0S1|1S0|1S1|0B1|1B0 \\ B \to 1B|0B|\epsilon $$

What should be my way of finding any pattern? to go each possible path independently ?


1 Answer 1


First, let us notice the following: $$ L(S) = \{ xyz \mid x,z \in \{0,1\}^*, |x|=|z|, y \in L(A) \} \\ L(A) = 0L(B)1 \cup 1L(B)0 \\ L(B) = (0+1)^* $$ Putting everything together, we get $$ L(G) = \{ x\sigma y \tau z \mid x,y,z \in \Sigma^*, \sigma,\tau \in \Sigma, |x|=|z|, \sigma \neq \tau \} $$ In other words, a word $w$ is in the language if there exists $i \leq |w|/2$ such that the $i$th symbol from the left is different from the $i$th symbol from the right. The condition $i \leq |w|/2$ can be eliminated, and we get that for some $i$, the $i$th symbol of $w$ is different from the $i$th symbol of $w^R$. In other words, $w \neq w^R$.

So your grammar generates the language of non-palindromes.

  • 1
    $\begingroup$ Thank you, so what I've gathered from here is that I should have tried to closely inspect the rule that makes the transition to a terminal letter and see what it imposes on the word. Thanks again! $\endgroup$
    – Tegernako
    Apr 30, 2020 at 14:25

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.