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.

  • 1
    $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. Have you tried reading through our reference material on this subject and applying it to your exercise? The methods there should work. Have you tried searching this site? You can find some related questions; I wouldn't be surprised if the techniques used for them can be used for your exercise too. cs.stackexchange.com/q/7224/755, cs.stackexchange.com/q/22846/755, cs.stackexchange.com/q/43008/755. $\endgroup$
    – D.W.
    Commented Sep 11, 2016 at 17:12
  • $\begingroup$ Have we not had this before? $\endgroup$
    – Raphael
    Commented Sep 13, 2016 at 8:49

1 Answer 1


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.


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.