# context free grammar of given language

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

• Where do all of these questions come from? Commented May 17, 2020 at 14:58
• wow, as I think about it, it's you, who only answers me! @YuvalFilmus Commented May 17, 2020 at 16:29

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