The prefixes of the string aabab are a, aa, aab, aaba, aabab. If the number of a's should be greater or equal to the number of b's, the grammar would be

S -> aS | aSbS | e,

but I need it with strictly more a's than b's in any prefix. I thought of this grammar, but I'm not sure it is correct.

S -> aS | aSAbA | a A -> aA | aAbA | e

  • 2
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. Did you try to prove that your grammar generates the correct langauge? $\endgroup$ Feb 1 '17 at 9:12

In short, take your grammar for the language having a greater or equal number of $a$'s in every prefix, but rename the startsymbol to $P$, i.e. $$ P \to aP \mid aPbP \mid \varepsilon. $$ Then simply note that your condition requires a word to start with an $a$, hence the following will do the job: $$ S \to aP. $$ For if $S \to w$ then $w = auv$ with $|u|_a \le |u|_b$, where $|u|_a$ denotes the number of $a$'s in $u$ (and analog for $|u|_b$), hence for the prefixes of $w$ the assertion follows. And conversely it works the same.

For your given grammar, this is correct (but I leave my answer as it seems to be simpler). For a proof note that if the produced word contains at least one $b$, then it must have at least two $a$'s before it, and this is what your production $aSAbA$ takes care of, where from $A$ we can just derive words having at most as many $a$'s as $b$'s in every prefix.

Let me give another approach to think about this. Might be a little bit to much theory, but just for education and reasoning. Note that the famous Dyck language is defined as $$ D := \{ w \in \{a,b\}^{\ast} : |u|_a \le |u|_b \mbox{for each prefix $u$ of $w$ and } |w|_a = |w|_b \}. $$ It is quite simple to give a grammar for this language, for example $$ S \to \varepsilon \mid SS \mid aSb. $$ Now if we denote by $\mbox{pref}(L)$ the set of prefixes of some language $L$ then your initial language of words having at most as many $a$'s as $b$'s in any prefix is $\mbox{pref}(D)$. And it is quite easy to derive a grammar from it, just make sure every production could be finished any time on the right (for a general argument see this post), hence we could give the grammar $$ S \to \varepsilon \mid SS \mid aSb \mid aS \mid a $$ where the production $S \to aS$ could also be leaved out. Now simply note that words fulfilling your restriction have to start with an $a$ and proceed as above.


the grammar you have written can't produce string "a".

but for a's strictly more than b's in any prefixes the grammar will be

S -> aA | aaAbA

A -> aAbA |aA |e

because if there is less/ equal no of a's is in the production before b's then it will produce error.

  • $\begingroup$ The grammar can produce "a" since I have S -> aS | aSAbA | a $\endgroup$
    – zaig
    Feb 1 '17 at 18:30
  • $\begingroup$ The OPs grammar is correct, as is yours. For a reasoning (and a simpler grammar obtained by that) see my answer. $\endgroup$
    – StefanH
    Feb 2 '17 at 15:44

One of the possible CFG's:

S->aPbPaP/aPaPbP/bPaPaP/PaP P->aPbPaP/aPaPbP/bPaPaP/PaP/ε

Even though S and P might look similar, P is required as S shouldn't produce ε by itself. This is because an ε string will be invalid, as number of a's should be greater than number of b's.

This grammar takes care of even those strings that begin with b.

examples of accepted strings: a, baaaaaa, aab,aba, aa, etc.

  • 1
    $\begingroup$ Welcome to the site! Sorry, but this is wrong, since it matches the string $baa$ which is not in the language (its prefix "$b$" contains more $b$s than $a$s). In addition, your suggested grammar is much more complicated than those that have already been suggested and, even if it were correct, you haven't given any explanation of why it works or why it would be better than the existing shorter solutions. $\endgroup$ Dec 3 '18 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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