2
$\begingroup$

I know the answer which is:

\begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbT\ \mid \varepsilon \end{align}

Now, $bbaaa$ is in the language. But the given CFG cannot generate it. Is it a possible misunderstanding on my end about the prefix's? Can you explain? And if the CFG given is wrong, what is the correct CFG for the language?

Maybe this is the right grammar?

\begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbS \mid bTaS\ \mid \varepsilon \end{align}

$\endgroup$
3
$\begingroup$

The string $bbaaa$ is not in the language, as Draconis pointed out (its prefix $b$ contains more $b$'s than $a$'s). As such, the second grammer is wrong.

However, the first suggestion is also wrong. It does not accept the string $abaaaa$, which belongs to the language.

The correct grammar is:

$$S \to \epsilon \mid aS \mid aSbS$$

To see that every word accepted by this grammar indeed belongs to the language, a straight-forward induction proof will do. So let's check that every word where each prefix has at least as many $a$'s as $b$'s is accepted by our grammar.

If the word is empty, we are done. Else it has to start with an $a$. There are two cases.

  • There is one prefix of the word that has an equal number of $a$'s and $b$'s. Write the word as $awbv$ where $awb$ is the shortest such prefix. Both $w$ and $v$ must belong to the language, so we can use the rule $S\to aSbS$.
  • Every prefix of the word has more $a$'s and $b$'s. Write the word as $aw$. Then $w$ must belong to the language, so we can use the rule $S \to aS$.
$\endgroup$

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.