Question

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

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

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

c) What is the language generated by G?

Short answer

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

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

c) \({\bf{L}}\left( {\bf{G}} \right){\bf{ = \{ }}{{\bf{1}}^{\bf{m}}}{{\bf{0}}^{\bf{n}}}{\bf{/m}} \ge {\bf{0,}}\,{\bf{n}} \ge {\bf{3\} }}\) 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 111000 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, S}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), and production are\({\bf{S}} \to {\bf{1S, S}} \to {\bf{00A, A}} \to {\bf{0A}}\), and\({\bf{ A}} \to {\bf{0}}\).

\(\begin{array}{c}{\bf{S}} \to {\bf{1S}}\\ \to {\bf{11S}}\\ \to {\bf{111S}}\\ \to {\bf{11100A}}\\ \to {\bf{111000}}\end{array}\)

Hence, 111000 belongs to the language generated by G.

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

Because of the productions

\(\begin{array}{l}{\bf{S}} \to {\bf{1S,}}\\{\bf{S}} \to {\bf{00A,}}\\{\bf{A}} \to {\bf{0A,}}\end{array}\)

And

\({\bf{A}} \to {\bf{0}}\)

Any sentence of the language generated by G ends with 0.

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

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

The production \({\bf{S}} \to {\bf{1S}}\) generates the strings of the form \({{\bf{1}}^{\bf{m}}}{\bf{s}}\) and the production

\({\bf{S}} \to {\bf{00A}}\), generates the strings of the form 000A with \({\bf{A}} \to {\bf{0A, A}} \to {\bf{0}}\)

Hence,\({\bf{L}}\left( {\bf{G}} \right){\bf{ = \{ }}{{\bf{1}}^{\bf{m}}}{{\bf{0}}^{\bf{n}}}{\bf{/m}} \ge {\bf{0,}}\,{\bf{n}} \ge {\bf{3\} }}\)is the language generated by G.