# Creating a regular grammar

Hi I am trying to write a grammar for $L=\{xcy \mid x \neq y^R \land x,y \in \{a,b\}^*\}$. I am not able to think beyond a point as to how to write the grammar. Could someone guide me?

-
are you sure this language is regular. clearly $c$ can not be in the pumping portion. what's about the word, say $a^{p-n}a^nca^{p+n}$, where $p$ is the pumping length and $a^n$ is the pumping portion, $1\leq n \leq p$. may be i am making some mistake.. – RSG Jun 18 '12 at 5:26

How can we generate strings of the form $\alpha c\beta$ where $\alpha, \beta\in\{a, b\}^*$ and $\alpha\ne \beta^R$? In cases like this, it's often helpful to work from the inside out, starting with the $c$ character, as @dtldarek indicated.

The central part will certainly be a separated palindrome of the form $\rho = \alpha c\alpha^R$ where $\alpha\in\{a, b\}^*$, if for no other reason than we'll always have at least the $c$ character. That's easy enough to generate: we just use the productions $$P\rightarrow aPa\mid bPb\mid c$$ Now, building outward from the string $\rho$, the only way we could fail to have a separated palindrome would be to have a string of one of these six forms:

1. $\alpha\ a\rho b\ \beta\qquad \alpha\ b\rho a\ \beta$
2. $\alpha a\rho\qquad \alpha b\rho\qquad \rho a\alpha\qquad \rho b\alpha$

where $\alpha, \beta\in\{a, b\}^*$.

In the first two cases (1) we have $\rho$ surrounded by two different characters, which can then be surrounded by any strings over $a$ and $b$. These can be generated by the productions \begin{eqnarray*} A &\rightarrow& aA\mid bA\mid Aa\mid Ab\mid U\\ U &\rightarrow& aPb\mid bPa \end{eqnarray*}

In the last cases (2), we have a mismatch caused by $\rho$ preceded by a nonempty string and followed by nothing at all or preceded by nothing and followed by a nonempty string. The first case may be generated by $$B\rightarrow aB\mid bB\mid P$$ and the second by $$C\rightarrow Ca\mid Cb\mid P$$ Finally, putting these pieces together yields a grammar for the target language: \begin{eqnarray*} S &\rightarrow& A\mid B\mid C\\ A &\rightarrow& aA\mid bA\mid Aa\mid Ab\mid U\\ U &\rightarrow& aPb\mid bPa\\ B &\rightarrow& aB\mid bB\mid P\\ C &\rightarrow& Ca\mid Cb\mid P\\ P &\rightarrow& aPa\mid bPb\mid c \end{eqnarray*}

-
This is really great! I was not able to come up with a strategy for this. I can understand this better now.! – Richa Sachdev Jun 18 '12 at 22:41
@Richa You can do somewhat the same construction to show {x#y | x, y in {a, b}* and x not equal to y} is a CFL. Give it a try. – Rick Decker Jun 19 '12 at 1:53
This seems to be wrong. Is you go from S->C->P->aPa->aca then we get a wrong result. Also I do not understand the need for both B and C to be same and they both have just one production from S. So which ever way you start we end the same place. – Richa Sachdev Jun 19 '12 at 14:20
@RichaSachdev Oops! I miscopied the C productions. It's fixed now---thanks for the catch. – Rick Decker Jun 20 '12 at 14:26

Hint:

1. $L$ is context free, but is not regular. If it was, then $$\overline{L \cup \{\Sigma^*c\Sigma^*c\Sigma^*\}} \cap \{a^*ca^*\} \cong \{a^nca^n\}$$ would also need to be.

2. Language $L_2 = \{a^*cb^*\}$, that means the first part (the $a$s), then something happens (the $c$), and the second part (the $b$s) can be written as \begin{align} S &\to aS \mid cT \\ T &\to bT \mid \varepsilon \end{align} where first part is created by $S$ and the second by $T$, and in the middle a $c$ is added (something happend). This is a useful technique that you can use to produce more complex grammars (e.g. there may be many parts, not just two and also those parts may generate non-terminals on both sides of themselves).

Hope that helps ;-)

-