0
$\begingroup$

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:

S->B
B->b | ABB | BAB | BAB | BBA
A->a

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?

$\endgroup$
2
  • $\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 '15 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 '15 at 2:20