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
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
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?