S → aS | aSbS | (empty) where the alphabet is {a,b}

in other words, the set of strings where any prefix has at least as many 'a's as 'b's.

  • $\begingroup$ What exactly are you asking for? It is not clear at all. You have given a grammar that does not do what you specify. $\endgroup$ – lPlant Jul 24 '14 at 15:50
  • $\begingroup$ sry about the typo! i gave an ambiguous grammar of that. what's an unambiguous one for it? $\endgroup$ – hollow7 Jul 24 '14 at 15:57

A grammar that can do this unambiguously is:

$S \to aS \mid A S \mid \epsilon$
$A \to a AAb \mid \epsilon$

Every b is associated with an a in front of it, and anything between these is also associated in the same way so there is always balance.


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