0
$\begingroup$

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\}$
where
$V=\{A,B,a,b\}$
$Σ=\{a,b\}$
$R=\{S\rightarrow aSa|bSb|aBb|bBa,$
$\ \ \ \ \ \ \ \ \ \ B\rightarrow aBa|bBb|aBb|bBa\}$

Is this correct?

I found a similar problem here.

$\endgroup$
2
  • 2
    $\begingroup$ Try to prove that it's correct. $\endgroup$ Mar 25, 2015 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, 2015 at 8:13

0