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.


closed as unclear what you're asking by lPlant, David Richerby, Wandering Logic, vonbrand, D.W. Jul 28 '14 at 5:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.