context free grammar of given language

Question

I wonder how can I find out what is context-free grammar of the following language?

$$ L_4 = \{w_1\#w_2 \mid w_1,w_2 \in \Sigma^*, w_1 \neq w_2^R \} $$

Answer 1

Assume $\Sigma = \{a,b\}$. We want to generate a word $w_1\#w_2$ is such that $w_1 \ne w_2^R$. There are two obvious possibilities:

1. $|w_1| = |w_2|$: In these words, there has to be at least one pair of positions equidistance from $\#$ such that the letters in these positions are different. Using the non-terminal $S_1$, we will generate the part of $w$ till we reach the first such pair; then we transition to non-terminal $S_2$ which will generate the opposite letters at that pair of position and move to the non-terminal $S_3$. From $S_3$, we are free to generate whatever we want. This will make sure that we have at least such pair of opposite letters, and hence $w_1 \ne w_2^R$.
   We can generate such words using following grammar: \begin{align} S_1 &\rightarrow aS_1a|bS_1b|S_2\\ S_2 &\rightarrow aS_3b|bS_3a\\ S_3 &\rightarrow aS_3a| bS_3b| aS_3b | bS_3a|\# \end{align}

2. $|w_1| \ne |w_2|$: In this case, with the non-terminal $P_1$ we will generate any word with equal number of letters on both side of $P_1$, and then we will move to either the non-terminal $P_2$ or $P_3$. With $P_2$ (or $P_3$) we will generate more letters either on the left side (or the right side) of $\#$. In the end, this will make sure that $|w_1| \ne |w_2|$. We can generate such words using the following grammar:

   \begin{align} P_1 &\rightarrow aP_1a| bP_1b| aP_1b | bP_1a| P_2 |P_3 \\ P_2 &\rightarrow aP_2|bP_2|a\# | b\#\\ P_3 &\rightarrow P_3a|P_3b|\#a | \#b\\ \end{align}

For the given language, the grammar would be: $S \rightarrow S_1|P_1$.