# CFG for $L=\{w_1cw_2:w_1\neq w_2^{R}\}$

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.

• 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.
– D.W.
Sep 11, 2016 at 17:12
• Have we not had this before?
– Raphael
Sep 13, 2016 at 8:49

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$)
• (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.