2
$\begingroup$

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?

  • 1
    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..2012-06-18

2 Answers 2

3

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

  • 0
    @RichaSachdev Oops! I miscopied the C productions. It's $f$ixed now---thanks $f$or the catch.2012-06-20
3

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 ;-)