# Write a Context Free Grammar for L = {x#y | x =/= reverse of y}

$x,y$ are in $\{0,1\}*$

So for example 10101#11111 is in the language, but 000111#111000 is not.

This just baffles me.

$S\to A\#B$

How do you prevent one side from being the reverse of the other?

-
–  Raphael Sep 29 '12 at 18:20

First generate any string as the initial part of $x$, and its reversal as the terminal part of $y$. These matching parts can be as long as you like (or empty).

$S\rightarrow 1S1 \;|\; 0S0.$

Then generate at least one character where $x$ and $y$'s reversal differ. If both are to be longer than the matching parts:

$S\rightarrow 1A\#A0 \;|\; 0A\#A1.$

If just one is to be longer:

$S\rightarrow 1A\#\;|\; 0A\#\;|\; \#A0\;|\; \#A1.$

Finally, fill in the wildcards with any strings at all:

$A\rightarrow 0A\;|\; 1A\;|\; \varepsilon.$

-

Thinking of the language as two strings (separated by $\#$) with corresponding pairs of characters (the first to the last etc.), what you need to do is ensure that there is at least one character pair that are not the same character, then after that one, you can pretty much do anything:

$$S \rightarrow 1S1\; |\; 0S0\; |\; 0A1 \; |\; 1A0 \; |\; \#B0 \;|\;\#B1\;|\;0B\#\;|\;1B\#\\ A \rightarrow 1A \; |\; A1\;|\;0A\;|\;A0\;|\; \#\\ B \rightarrow 0B\;|\;1B\;|\;\varepsilon$$

So, assuming I haven't mucked any of the details up, the grammar matches the pairs off until it finds something that doesn't match (i.e. the $x \neq y^{\mathcal{R}}$). This can happen in two ways, either the you get a $1$ and a $0$, or one string is shorter than the other, so you hit the $\#$ character.

-

Think about how you might test a string to see whether it belongs to $L$. Probably the easiest way is to start at the $\#$ and work outwards until you find a pair of unmatched characters or reach the end of the string simultaneously at both ends. For example, with $\color{green}{1}\color{red}{1}\color{blue}{0}0\#0\color{blue}{0}\color{red}{1}\color{green}{0}$ I’d be able to match up the black $0$’s, the blue $0$’s, and the red $1$’s, but the green $1$ and $0$ don’t match, so the word is in $L$. Similarly, $1100\#001\in L$ because I run out of characters on the right before I run out on the left: the left-most $1$ doesn’t match $\epsilon$. But $1100\#0011\notin L$, since I find no mismatches and run out of characters at the same time on both sides.

Now turn this scanning procedure into a generating procedure by running it backwards. The productions $$A\to A0\mid 0\mid A1\mid 1$$ generate any non-empty string of $0$’s and $1$’s; those will go on the outside ends of the string. Just inside them we’ll generate an unmatched pair, optionally followed by an arbitrary string on one or both ends:

$$S\to 0T1\mid 1T0\mid 0T1A\mid 1T0A\mid A0T1\mid A1T0\mid A0T1A\mid A1T0A$$

At this point we can generate anything of the form $\alpha aSb\beta$, where $\alpha,\beta\in\{0,1\}^*$, $a,b\in\{0,1\}$, and $a\ne b$. Now we want to generate the matched pairs in the middle, if there are any:

$$T\to 0T0\mid 1T1\mid \#$$

takes care of that. The final set of productions:

\begin{align*} &S\to 0T1\mid 1T0\mid 0T1A\mid 1T0A\mid A0T1\mid A1T0\mid A0T1A\mid A1T0A\\ &A\to A0\mid 0\mid A1\mid 1\\ &T\to 0T0\mid 1T1\mid \# \end{align*}

-