Question

Construct a derivation of \({{\bf{0}}^{\bf{2}}}{{\bf{1}}^{\bf{2}}}{{\bf{2}}^{\bf{2}}}\) in the grammar given in Example 7.

Short answer

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

\(\begin{array}{c}{\bf{S}} \Rightarrow {\bf{0SAB}}\\ \Rightarrow {\bf{00SABAB}}\\ \Rightarrow {\bf{00ABAB}}\\ \Rightarrow {\bf{00 AABB}}\\ \Rightarrow {\bf{001ABB}}\\ \Rightarrow {\bf{0011BB}}\\ \Rightarrow {\bf{00112B}}\\ \Rightarrow {\bf{001122}}\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 7.

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

\({\bf{S}} \to {\bf{0SAB}}\),\({\bf{S}} \to {\bf{\lambda }}\), \({\bf{BA}} \to {\bf{AB, 0A}} \to {\bf{01, 1A}} \to {\bf{11, 1B}} \to {\bf{12}}\) and \({\bf{2B}} \to {\bf{22}}\)

Where \({\bf{\lambda }}\) is empty.

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

We have,

\(\begin{array}{*{20}{l}}{{\bf{S}} \to {\bf{0SAB}}}\\{{\bf{\;\;\;}}\,\, \to {\bf{0}}\left( {{\bf{0SAB}}} \right){\bf{ AB}}}\\{{\bf{\;\;\;}}\,\, \to {\bf{00\lambda ABAB}}}\\{{\bf{\;\;\;}}\,\, \to {\bf{00A(AB)B}}}\\{{\bf{\;\;\;}}\,\, \to {\bf{001ABB}}}\\{{\bf{\;\;\;}} \to {\bf{0011BB}}}\\{{\bf{\;\;\;}} \to {\bf{00112B}}}\\{{\bf{\;\;\;}} \to {\bf{001122}}}\end{array}\)

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