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.

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

 
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.