-2
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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.

$\endgroup$

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