Question

a) Construct a derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{1}}}\) in Example 6.

b) Construct a derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{2}}}\) in Example 6.

Short answer

(a) derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{1}}}\) is:

\(\begin{array}{c}{\bf{S}} \to {\bf{0S}}\\ \to {\bf{0}}\left( {{\bf{0S}}} \right)\\ \to {\bf{00}}\left( {{\bf{S1}}} \right)\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{1}}\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{11}}\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{111 }}\\ \to {\bf{00\lambda 1111 }}\\ \to {{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\end{array}\)

(b) derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{2}}}\) is:

\(\begin{array}{c}{\bf{S}} \to {\bf{0S}}\\ \to {\bf{0}}\left( {{\bf{0S}}} \right)\\ \to {\bf{00}}\left( {{\bf{1A}}} \right)\\ \to {\bf{001}}\left( {{\bf{1A}}} \right)\\ \to {\bf{0011}}\left( {{\bf{1A}}} \right)\\ \to {\bf{00111}}1{\bf{ }}\\ \to {{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\end{array}\)

Step-by-step solution

about the language generated by the grammar.

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be a phrase-structure grammar. The language generated by G (or the language of G), denoted by L(G), is the set of all strings of terminals that are derivable from the starting state S.

Firstly, we shall construct a derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{1}}}\) in Example 6.

\({{\bf{G}}_{\bf{1}}}{\bf{ = }}\left( {{\bf{V, T, S, P}}} \right)\)is the phrase structure grammar with\({\bf{V = }}\left\{ {{\bf{0, 1, S}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), S is the starting symbol and the production are\({\bf{S}} \to {\bf{0S, S}} \to {\bf{S1}}\),\({\bf{S}} \to {\bf{\lambda }}\), where \({\bf{\lambda }}\) is the empty.

\(\begin{array}{c}{\bf{S}} \to {\bf{0S}}\\ \to {\bf{0}}\left( {{\bf{0S}}} \right)\\ \to {\bf{00}}\left( {{\bf{S1}}} \right)\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{1}}\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{11}}\\ \to {\bf{00}}\left( {{\bf{S1}}} \right){\bf{111 }}\\ \to {\bf{00\lambda 1111 }}\\ \to {{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\end{array}\)

Hence\({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\)is a sentence of the language of the grammar\({{\bf{G}}_{\bf{1}}}\).

Now, we shall construct a derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\) using the grammar \({{\bf{G}}_{\bf{2}}}\) in Example 6.

\({{\bf{G}}_{\bf{2}}}{\bf{ = }}\left( {{\bf{V, T, S, P}}} \right)\) is the phrase structure grammar with\({\bf{V = }}\left\{ {{\bf{S, A, 0, 1}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), S is the starting symbol and the production are \({\bf{S}} \to {\bf{0S, S}} \to {\bf{1A, S}} \to {\bf{1, A}} \to {\bf{1A, A}} \to {\bf{1}}\) and\({\bf{S}} \to {\bf{\lambda }}\).

Where,\({\bf{\lambda }}\) is the empty string.

\(\begin{array}{c}{\bf{S}} \to {\bf{0S}}\\ \to {\bf{0}}\left( {{\bf{0S}}} \right)\\ \to {\bf{00}}\left( {{\bf{1A}}} \right)\\ \to {\bf{001}}\left( {{\bf{1A}}} \right)\\ \to {\bf{0011}}\left( {{\bf{1A}}} \right)\\ \to {\bf{001111 }}\\ \to {{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\end{array}\)

Hence,\({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{4}}}\)is a sentence of the language of the grammar\({{\bf{G}}_{\bf{2}}}\).