# Finding an unambiguous grammar of a language provided by a CFG

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.

• The original grammar generates the language of all words in which in every prefix, there are at least as many $a$s as $b$s. – Yuval Filmus Apr 13 '19 at 21:18
• Your grammar is ambiguous: $ababab$ has two different parse trees. – Yuval Filmus Apr 13 '19 at 21:19

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

• I appreciate the thoroughness of your response and the unambiguous grammar provided. I would like to ask, do you have any resources where I can learn heuristics on how to create unambiguous grammars? – Denzak Apr 14 '19 at 4:13
• I’m not aware of any, though in a way, literature on yacc or LL grammars should be relevant. – Yuval Filmus Apr 14 '19 at 5:02