StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q8E

Expert-verifiedFound in: Page 856

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**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{\} }}\).**

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.

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.

\({\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.

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.**

94% of StudySmarter users get better grades.

Sign up for free