Finding an unambiguous grammar of a language provided by a CFG

Question

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.

In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar for the language of this Context-Free Grammar (where epsilon is the empty string):

$$S \rightarrow aS | aSbS | \epsilon$$

I'm having difficulty describing this grammar formally, but I realize the number of a's is greater than or equal to the number of b's. And the string will always begin with an a (except for the empty string).

I have attempted to break the grammar into two parts to remove the ambiguity. After a few brute force attempts, I decided to distinctly have a variable generate only a's and the other variable generate an equal amount of a's and b's.

$$S \rightarrow A | B | \epsilon$$ $$A \rightarrow aA | a $$ $$B \rightarrow BB | aAbA | ab$$

The key part is when a re-write of B to a sentential form when an A occurs, only more a's can be generated in the string.

My question is does the new grammar I created generate the same language as the previous grammar? If not, what would be the correct grammar? I realize determining if two CFG are equivalent is undecidable; but I have no method of determining if I am correct.

Answer 1

First, let us show that the original grammar generates the language $L$ of all words in which in every prefix, there are at least as many $a$s as $b$.

A simple induction shows that every word generated by the grammar satisfies the property. In the other direction, let $w$ be a non-empty word in $L$. We consider two cases:

1. Some prefix of $w$ has exactly as many $a$s as $b$s. Write $w = axby$, where $axb$ is the shortest prefix with this property. This choice guarantees that $x \in L$. Also, $y \in L$. Hence we can generate $w$ using the rule $S \to aSbS$.

2. In every prefix of $w$, the number of $a$s exceeds the number of $b$s. Hence $w = az$, where $z \in L$, and we can generate $w$ using the rule $S \to aS$.

Every word $w \in L$ can be written (uniquely) as $w_0 a w_1 a \cdots a w_\ell$, where $w_i$ is a word in $L$ in which the number of $a$s is the same as the number of $b$s. Indeed, $w_0$ is the longest prefix of $w$ in which the number of $a$s is the same as the number of $b$s; $w_0 a w_1$ is the longest prefix of $w$ in which the number of $a$s exceeds the number of $b$s by 1; and so on.

Suppose that $T$ generates unambiguously the language $L'$ of all words in $L$ in which the number of $a$s is the same as the number of $b$s. Then we can generate $L$ itself unambiguously using the productions $S \to T a S \mid T$. The language $L'$ can be generated unambiguously using $T \to aTbT \mid \epsilon$.