Question

Construct a derivation of \({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\) using the grammar given in Example 5.

Short answer

The derivation of\({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\)is:

\(\begin{array}{c}{\bf{S}} \to {\bf{0S1 }}\\ \to {\bf{0}}\left( {{\bf{0S1}}} \right){\bf{1}}\\ \to {\bf{0(0}}\left( {{\bf{0S1}}} \right){\bf{1)1 }}\\ \to {\bf{000\lambda 111 }}\\ \to {\bf{000111}}\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, using the grammar given in Example 5

\({\bf{G = }}\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\}\) and the productions are

\({\bf{S}} \to {\bf{0S1}}\),\({\bf{S}} \to {\bf{\lambda }}\), where \({\bf{\lambda }}\) is the empty string.

Now, we shall construct a derivation of \({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\)

We have,

\(\begin{array}{c}{\bf{S}} \to {\bf{0S1 }}\\ \to {\bf{0}}\left( {{\bf{0S1}}} \right){\bf{1}}\\ \to {\bf{0(0}}\left( {{\bf{0S1}}} \right){\bf{1)1 }}\\ \to {\bf{000\lambda 111 }}\\ \to {\bf{000111}}\end{array}\)

Hence,\({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\)is a sentence of the language generated by G.