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?
 A: Hint:


*

*$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.

*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 ;-)
A: 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:


*

*$\alpha\ a\rho b\ \beta\qquad \alpha\ b\rho a\ \beta$

*$\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*}
