I am trying to construct a context-free grammar for the following language: $$L=\{w_1cw_2:w_1\neq w_2^{R}\},$$ where words are over $\{a,b,c\}$.

I have tried to do this by taking the union of two sub-languages:

  1. The length of $w_1$ is not equal to the length of $w_2$.
  2. The lengths are equal.

For 1, I've already written the grammar. But I'm having difficulty with 2. In terms of a PDA I think non-determinism can solve this. However, what is the CFG for 2? If I can find it, I will union 1 and 2 to get the final solution.


Here's a hint for part (2): work from the inside out. A string of the form $w_1cw_2$ where $|w_1|=|w_2|$ is "matched" ($w_1=w_2^R$) if and only if it is of the form

  • $c$, or
  • (any character $x$) ("matched" string) (character $x$)

Similarly, such a string is "unmatched" if and only it is of the form

  • (any character) ("unmatched" string) (any character), or
  • (any character $x$) ("matched" string) (any character $y\ne x$)

Thus, we can make a grammar where the "matched" strings are generated by $$ M\rightarrow c\mid aMa\mid bMb\mid cMc $$ We can make the "unmatched" strings ($w_1\ne w_2$) generated by similar productions, which I'll let you do, using the variable $U$. Finally, you want to generate "unmatched" strings, so $U$ will be the start variable for your grammar.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.