6. There are two leftmost derivations for w = aab.
9. From the dfa for a regular language we can get a regular grammar by the
method of Theorem 3.4. The grammar is an s-grammar except for q f → λ.
But this rule does not create any ambiguity. Since the dfa never has a choice,
there is never any choice in the production that can be applied.
14. Ambiguity of the grammar is obvious from the derivations
An equivalent unambiguous grammar is
It is not easy to see that this grammar is unambiguous. To make it plausible,
consider the two typical situations, w = aabb, which can only be derived by
starting with A → aAb, and w = abab, which can only be derived by starting
with A → AA. More complicated strings are built from these two situations,
so they can be parsed only in one way.
20. Solution:
Chapter 6
Section 6.1
3. Use the rule in Theorem 6.1 to substitute for B in the first grammar. Then B
becomes useless and the associated productions can be removed. By
Theorems 6.1 and 6.2 the two grammars are equivalent.
9. From the dfa for a regular language we can get a regular grammar by the
method of Theorem 3.4. The grammar is an s-grammar except for q f → λ.
But this rule does not create any ambiguity. Since the dfa never has a choice,
there is never any choice in the production that can be applied.
14. Ambiguity of the grammar is obvious from the derivations
An equivalent unambiguous grammar is
It is not easy to see that this grammar is unambiguous. To make it plausible,
consider the two typical situations, w = aabb, which can only be derived by
starting with A → aAb, and w = abab, which can only be derived by starting
with A → AA. More complicated strings are built from these two situations,
so they can be parsed only in one way.
20. Solution:
Chapter 6
Section 6.1
3. Use the rule in Theorem 6.1 to substitute for B in the first grammar. Then B
becomes useless and the associated productions can be removed. By
Theorems 6.1 and 6.2 the two grammars are equivalent.