• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q8E

Expert-verified
Found in: Page 856

### Discrete Mathematics and its Applications

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.

See the step by step solution

## Step 1: 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.

## Step 2: 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.

## Step 3: 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.