Question

show that the grammar given in Example 5 generates the set \({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\).

Short answer

Proved, \({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\) is the language of the grammar G.

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\}\), S is the starting symbol and the production are

\({\bf{S}} \to {\bf{0S1}}\), \({\bf{S}} \to {\bf{\lambda }}\).

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

Now, it shall show that the grammar given in Example 5 generates the set \({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\)

The production \({\bf{S}} \to {\bf{0S1}}\) with \({\bf{S}} \to {\bf{\lambda }}\) generates the string 0 1.

Applying the production \({\bf{S}} \to {\bf{0S1}}\) twice and with \({\bf{S}} \to {\bf{\lambda }}\) generates the string 0011.

Similarly applying the production \({\bf{S}} \to {\bf{0S1}}\) n times and with \({\bf{S}} \to {\bf{\lambda }}\) generates the string \({{\bf{0}}^{\bf{3}}}{{\bf{1}}^{\bf{3}}}\).

Hence,\({\bf{\{ }}{{\bf{0}}^{\bf{n}}}{{\bf{1}}^{\bf{n}}}{\bf{|}}\,{\bf{n = 0,}}\,{\bf{1,}}\,{\bf{2,}}\,...{\bf{\} }}\)is the language of the grammar G.