I need to find a grammar that generates the language composed by all words that have more $a$ than $b$ given an alphabet $\{a,b\}$

I tried the following production rules:

B->b | ABB | BAB | BAB | BBA

with this rules it's fairly simple to proof that all the words that the grammar generates are made up with more $a$ than $b$.

How can I proof that all words made up with more $a$ than $b$ can be generated that way?

  • $\begingroup$ You don't really need the $A \to a$ rule (you could just write the $B \to aBB$ for example. also you have $B \to BAB$ twice. $\endgroup$
    – wvxvw
    Sep 29, 2015 at 23:07
  • $\begingroup$ That set of production rules implements a grammar accepting more bs than as, not vice versa. It's also rather redundant. You could just use the rule S -> a | aS | bSS | SbS | SSb. $\endgroup$
    – TLW
    Oct 1, 2015 at 2:20


Browse other questions tagged or ask your own question.