Question

Find a phrase-structure grammar that generates the set \(\left\{ {{{\bf{0}}^{{{\bf{2}}^{\bf{n}}}}}\mid {\bf{n}} \ge 0} \right\}\).

Short answer

The phase-structure grammar:

\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\)

\({\bf{V = }}\left\{ {{\bf{S,0,1}}} \right\}\)Alphabet

\({\bf{T = }}\left\{ {{\bf{0,1}}} \right\}\)Set of terminal symbols

\({\bf{S}}\)Start symbol

Set of productions \({\bf{P}}\)

\(\begin{array}{l}{\bf{S}} \to {\bf{C0B}}\\{\bf{C}} \to {\bf{CA}}\\{\bf{C}} \to {\bf{\lambda }}\\{\bf{A0}} \to {\bf{00A}}\\{\bf{AB}} \to {\bf{B}}\\{\bf{B}} \to {\bf{\lambda }}\end{array}\)

Step-by-step solution

Definition

An alphabet is a set of elements that can be used to construct strings.

A language is a subset of the set of all possible strings over an alphabet.

Phase structure grammar \(\left( {{\bf{V, T, S, P}}} \right)\) shows the description of a language, \({\bf{V}}\) is the alphabet, (T) is a set of terminal symbols, \({\bf{S}}\) is the start symbol and \({\bf{P}}\) is a set of productions.

Finding the phase-structure

It is given that \(\left\{ {{{\bf{0}}^{{{\bf{2}}^{\bf{n}}}}}\mid {\bf{n}} \ge 0} \right\}\).

The set of terminal symbols of all possible symbols in the resulting strings.

\({\bf{T = }}\left\{ {{\bf{0,1}}} \right\}\)

Let \({\bf{S}}\) be the start state.

It will construct the grammar by initially generating strings of the form \({\bf{AA \ldots A0B}}\) with zero or more \({\bf{A's}}\) on the left, a \(0\) in the middle and \({\bf{B}}\) on the right.

\({\bf{S}} \to {\bf{C0B}}\)

\(\begin{array}{l}{\bf{C}} \to {\bf{CA}}\\{\bf{C}} \to {\bf{\lambda }}\end{array}\)

Doubling the values

Next, it needs to cause the doubling of the \({\bf{0's}}\) using the \({\bf{A's}}\):

\({\bf{A0}} \to {\bf{00A}}\)

It will use this rule until the \({\bf{A's}}\) reach the \({\bf{B}}\) on the right. Once the \({\bf{A's}}\) reach the \({\bf{B's}}\), It absorbs the \({\bf{D's}}\) in the \({\bf{E's}}\).

\({\bf{AB}} \to {\bf{B}}\)

Finally, It needs to remove the \({\bf{B}}\) symbol, which is done by sending it to the empty string \({\bf{\lambda }}\).

\({\bf{B}} \to {\bf{\lambda }}\)

The alphabet \({\bf{V}}\) contains all symbols used in the production steps above.

\({\bf{V = }}\left\{ {{\bf{S, 0,1}}} \right\}\)

Combining the values

Combining all this information.

Therefore, it obtains the phase-structure grammar:

\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\)

\({\bf{V = }}\left\{ {{\bf{S, 0,1}}} \right\}\)Alphabet

\({\bf{T = }}\left\{ {{\bf{0,1}}} \right\}\)Set of terminal symbols

\({\bf{S}}\)Start symbol

Set of productions \({\bf{P}}\)

\(\begin{array}{l}{\bf{S}} \to {\bf{C0B}}\\{\bf{C}} \to {\bf{CA}}\\{\bf{C}} \to {\bf{\lambda }}\\{\bf{A0}} \to {\bf{00A}}\\{\bf{AB}} \to {\bf{B}}\\{\bf{B}} \to {\bf{\lambda }}\end{array}\)