Question

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}}\) and \({\bf{S}} \to 0\) is unambiguous.

Short answer

\({\bf{G}}\) is unambiguous.

Step-by-step solution

Definition

In mathematics, a well-defined expression or an unambiguous expression is an expression whose definition gives it a unique interpretation or value. Otherwise, the expression is said to be not well defined or ambiguous.

Given:

\(\begin{array}{l}{\bf{G = (V,T,S,P)}}\\{\bf{V = \{ 0,S\} }}\\{\bf{T = \{ 0\} }}\\{\bf{S}} \to 0{\bf{S}}\\{\bf{S}} \to 0\end{array}\)

Proving that \({\bf{G}}\) is unambiguous

To proof: \({\bf{G}}\) is unambiguous (that is, there is exactly one way to derive every string in the grammar \({\bf{G}}\))

PROOF

Let \({\bf{x}}\) be a string that is generated by \({\bf{G}}\).

Let the length of \({\bf{x}}\) be \({\bf{n}}\) with \({\bf{n}}\) a positive integer. Note: \({\bf{n = 0}}\) is impossible as \({\bf{G}}\) does not generate the empty string \({\bf{\lambda }}\).

There is only one way to construct a string of length \({\bf{n}}\), that is, by using the production rule \({\bf{S}} \to 0{\bf{Sn - }}1\) times and then use the production rule \({\bf{S}} \to {\bf{0}}\) once. it will then obtain \({\bf{x = }}{{\bf{0}}^{\bf{n}}}\).

It cannot use any other productions rule nor any other combination of productions rule to obtain \({{\bf{0}}^{\bf{n}}}\) and thus the derivation tree of \({{\bf{0}}^{\bf{n}}}\) is unique.

Therefore, it gets \({\bf{G}}\) is unambiguous.