Question

A context-free grammar is ambiguous if there is a word in \({\bf{L(G)}}\) with two derivations that produce different derivation trees, considered as ordered, rooted trees.

Show that the grammar \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) with \({\bf{V = }}\left\{ {{\bf{0, S}}} \right\}{\bf{,T = }}\left\{ {\bf{0}} \right\}\), starting state \({\bf{S}}\), and productions \({\bf{S}} \to {\bf{0S,S}} \to {\bf{S0}}\), and \({\bf{S}} \to 0\) is ambiguous by constructing two different derivation trees for \({{\bf{0}}^{\bf{3}}}\).

Short answer

The idea is that the rules allow us to add \({\bf{0's}}\) either to the right or the left. So, it can get three \({\bf{0's}}\) in several ways, depending on which side it adds the \({\bf{0's}}\) on.

Step-by-step solution

Definition

An expression is said to be ambiguous (or poorly defined) if its definition does not give it a unique interpretation or value. An unambiguous expression is said to be well-defined.

Using the ambiguous definition

The idea is that the rules allow us to add \({\bf{0's}}\) either to the right or the left. Therefore, it can get three \({\bf{0's}}\) in a number of ways, depending on which side it adds the \({\bf{0's}}\) on.