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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.