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

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

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


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.