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 ?
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.
