This question already has an answer here:

I am trying to find a context free grammar for the language

$L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$

where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible solution: $G=\{V,Σ,R,S\}$
$R=\{S\rightarrow aSa|bSb|aBb|bBa,$
$\ \ \ \ \ \ \ \ \ \ B\rightarrow aBa|bBb|aBb|bBa\}$

Is this correct?

I found a similar problem here.


marked as duplicate by D.W., Luke Mathieson, David Richerby, Raphael Mar 26 '15 at 8:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Try to prove that it's correct. $\endgroup$ – Yuval Filmus Mar 25 '15 at 20:03
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael Mar 26 '15 at 8:13