Help with context free grammar excercise

Question

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.

Answer 1

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} $$