Question

Question:Let G = (V, T, S, P) be the phrase-structure grammar with V = {0, 1, A, B, S}, T = {0, 1}, and set of productions P consisting of S → 0A, S → 1A, A → 0B, B → 1A, B → 1.

a) Show that 10101 belongs to the language generated by G.

b) Show that 10110 does not belong to the language generated by G.

c) What is the language generated by G?

Short answer

a) Proved, 10101 belongs to the language generated by G.

b) Proved, 10110 does not belong to the language generated by G.

c) \({\bf{\{ 0}}{\left( {{\bf{0,1}}} \right)^{\bf{n}}}{\bf{/n}} \ge {\bf{1\} U\{ 1}}{\left( {{\bf{01}}} \right)^{\bf{n}}}{\bf{/n}} \ge {\bf{1\} }}\), is the language generated by 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.

We shall show that 10101 belongs to the language generated by G.

Use the given information,

Let \({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\) be the phrase-structure grammar with\({\bf{V = }}\left\{ {{\bf{0, 1, A, B, S}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), and production are \({\bf{S}} \to {\bf{0A, S}} \to {\bf{1A, A}} \to {\bf{0B, B}} \to {\bf{1A}}\)and\({\bf{B}} \to {\bf{1}}\).

\(\begin{array}{c}{\bf{S}} \to {\bf{1A}}\\ \to {\bf{10B}}\\ \to {\bf{101A}}\\ \to {\bf{1010B}}\\ \to {\bf{10101}}\end{array}\)

Hence, 10101 belongs to the language generated by G.

We shall Show that 10110 does not belong to the language generated by G.

\(\begin{array}{c}{\bf{S}} \to {\bf{1A}}\\ \to {\bf{10B}}\\ \to {\bf{101A}}\\ \to {\bf{101A}}\end{array}\)

And A product the strings of form 01, 0101,...

Hence, 10110 does not belong to the language generated by G.

We need to find what is the language generated by G.

\(\begin{array}{c}{\bf{A}} \to {\bf{0B\;}}\\ \to {\bf{01}}\end{array}\)

\(\begin{array}{c}{\bf{A}} \to {\bf{0B}}\\ \to {\bf{01A}}\\ \to {\bf{010B}}\\ \to {\bf{0101}}\end{array}\)

\(\begin{array}{c}{\bf{A}} \to {\bf{0B}}\\ \to {\bf{01A}}\\ \to {\bf{010B}}\\ \to {\bf{0101A}}\\ \to {\bf{01010B}}\\ \to {\bf{010101}}\end{array}\)

Therefore, A produces the strings of the form \({\left( {{\bf{01}}} \right)^{\bf{n}}}\) for all \({\bf{n}} \ge {\bf{1}}\) , and because

\({\bf{S}} \to {\bf{0A, S}} \to {\bf{1A}}\)

Hence,\({\bf{\{ 0}}{\left( {{\bf{0,1}}} \right)^{\bf{n}}}{\bf{/n}} \ge {\bf{1\} U\{ 1}}{\left( {{\bf{01}}} \right)^{\bf{n}}}{\bf{/n}} \ge {\bf{1\} }}\)is the language generated by G.