# Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language:

$$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$

meaning every string with any number of $$a$$'s, $$b$$'s and $$c$$'s in that order, with the amount of $$a$$'s greater than the amount of $$c$$'s and the amount of $$b$$'s greater than zero.

I am having trouble figuring out the rule that makes sure there are more $$a$$s than $$c$$s.

I have: \begin{align}S&\to aABC | ab\\ A&\to aA | a\\ B&\to bB | b\\ C&\to cC | c\\ \end{align} I know this is wrong because I should be adding an $$a$$ every time I add a $$c$$, but I don't know how to write that.

I think you can do it in this way

\begin{align} X&\to A\ |\ aXc\ |\ aAc\\ A&\to aA_t\\ A_t&\to aA_t\ |\ B\\ B&\to bB_t\\ B_t&\to bB_t\ |\ \epsilon\\ \end{align}

Here $$X$$ can choose to do the first transformation, if there are not going to be any $$c$$s. $$X$$ can do the second transformation many times to add an initial chunk of the same amount of $$a$$s and $$c$$s, or do the third transformation to put a last pair of an $$a$$ and a $$c$$.

In that third case, it goes to $$A$$ which puts one extra $$a$$ and goes to $$A_t$$, which can put even more $$a$$s or go to put $$b$$s.

Then $$B$$ puts one $$b$$ and goes to $$B_t$$, which puts as many more $$b$$s as wanted or terminates.

But check it. This is the first ever context free grammar rules that I write in my life.

Shorter rules by nir shahar

\begin{align} S&\to AB\ |\ aSc\\ A&\to aA\ |\ a\\ B&\to bB\ |\ b \end{align}

• This seems correct, however you can shorten the grammer. – nir shahar Jul 6 '20 at 21:20
• I have submitted an edit request :) – nir shahar Jul 6 '20 at 21:24
• @nirshahar And it looks like that is the smallest. – plop Jul 6 '20 at 21:31
• "shortest" is such a red flag :-) $$S\to T\mid aSc\\ T\to a\mid aT\mid Tb$$. – rici Jul 6 '20 at 21:46
• @johnl: alas, one symbol longer. Quite right. – rici Jul 7 '20 at 23:06