Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Please check if the formula for $L$ is alright after the edit. Also, it would be helpful if you could provide some context, e.g. is this a homework question (if yes, there is an appropriate tag for that)? –  dtldarek Jun 18 '12 at 5:07
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.. –  RSG Jun 18 '12 at 5:26

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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 ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.