0
$\begingroup$

I'm trying to find the CFG of language $L = \{ a^p b^q c^r \mid q = p+r > 0 \}$ but I'm completely stuck. I have no idea where to start.

Any advice would be very appreciated thank you

1 Answers 1

3

You need to generate at least one $b$, and you need to make sure that every time you generate a $b$, you also generate either an $a$ on the left or a $c$ on the right. You also have to make sure that the $a$’s all precede the $b$’s, which precede the $c$’s. One way to do this is to begin by generating $a^pb^p$ for $p\ge 0$, making sure that at the end of this process we can continue generating $b$’s and $c$’s on the righthand end of the string:

$\begin{align*} &S\to AC\mid C\\ &A\to aAb\mid ab \end{align*}$

This bit of grammar, with $S$ as initial symbol, generates all strings of the form $a^pb^pC$ for $p\ge 0$. Now add a production to let $C$ generate $b^rc^r$:

$\begin{align*} &S\to AC\mid C\\ &A\to aAb\mid ab\\ &C\to bCc\mid bc \end{align*}$

This almost works: it’s easy to see that every word that it generates is in $L$, and that it generates almost every word of $L$. Unfortunately, it always generates at least one $c$, so it generates every word of $L$ except $ab$. Can you make the very easy modification that repairs this omission?

  • 0
    @Momagic: You’re making it much too hard: just replace $S\to AC\mid C$ by $S\to AC\mid C\mid ab$. Everything remains the same, except that you now also have the derivation $S\to ab$ to give you the missing word.2012-04-04