Take the 2-minute tour ×

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

share|improve this question

1 Answer 1

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?

share|improve this answer
Would that fix be B → aBb | ab? –  Momagic Apr 4 '12 at 10:34
@Momagic: You have no non-terminal symbol $B$ on the righthand side of any of the existing production, so $B\to aBb\mid ab$ wouldn’t do anything. You’re missing only the one word $ab$. The grammar $S\to ab$ generates this word. How can you combine this with what I already have to get a CFG that generates $L$? –  Brian M. Scott Apr 4 '12 at 10:43
would that be S → abAC ∣ C? –  Momagic Apr 4 '12 at 16:54
@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. –  Brian M. Scott Apr 4 '12 at 20:30

Your Answer


