Question

Find a phrase-structure grammar for each of these languages.

a) the set consisting of the bit strings 10, 01, and 101.

b) the set of bit strings that start with 00 and end with one or more 1s.

c) the set of bit strings consisting of an even number of 1s followed by a final 0.

d) the set of bit strings that have neither two consecutive 0s nor two consecutive 1s.

Short answer

(a) The phase structure grammar is\({\bf{S}} \to {\bf{10, S}} \to {\bf{01, S}} \to {\bf{101}}\).

(b) The phase structure grammar is:

\({\bf{S}} \to {\bf{00AB, A}} \to {\bf{AA, A}} \to {\bf{0, A}} \to {\bf{1, B}} \to {\bf{BB, B}} \to {\bf{1}}\).

(c) The phase structure grammar is:

\({\bf{S}} \to {\bf{A0}}\),\({\bf{A}} \to {\bf{\lambda }}\)\({\bf{A}} \to {\bf{BBC, A}} \to {\bf{BCB, A}} \to {\bf{CBB, C}} \to {\bf{CC, B}} \to {\bf{CB, B}} \to {\bf{BC, B}} \to {\bf{1, C}} \to {\bf{0}}\)

(d) The phase structure grammar is,\({\bf{S}} \to {\bf{A, A}} \to {\bf{AA, A}} \to {\bf{A0, A}} \to {\bf{01}}\), \({\bf{A}} \to {\bf{\lambda }}\), \({\bf{S}} \to {\bf{B, B}} \to {\bf{BB, B}} \to {\bf{B1, B}} \to {\bf{10}}\),\({\bf{B}} \to {\bf{\lambda }}\)

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.

Now, we shall find a phrase-structure grammar for part (a) languages.

Consider the following language:

\({\bf{L = }}\left\{ {{\bf{10, 01, 101}}} \right\}\)

Then, the phrase structure grammar which generates the language L is\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\). If\({\bf{V = }}\left\{ {{\bf{0, 1, S}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), S is the starting symbol and the productions are as below;

\({\bf{S}} \to {\bf{10, S}} \to {\bf{01, S}} \to {\bf{101}}\).

Hence, phase structure grammar for the language is\({\bf{S}} \to {\bf{10, S}} \to {\bf{01, S}} \to {\bf{101}}\).

Now, we shall find a phrase-structure grammar for part (b) languages.

Consider the following language:

\({\bf{L = }}\left( {{\bf{a: a is a bit string that start with 00 and end with one or more 1s}}} \right)\)

Then, the phrase structure grammar which generates the language L is\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\). If\({\bf{V = }}\left\{ {{\bf{0, 1, S, A, B}}} \right\}{\bf{, T = }}\left\{ {{\bf{0, 1}}} \right\}\), S is the starting symbol and the productions are as below;

\({\bf{S}} \to {\bf{00AB, A}} \to {\bf{AA, A}} \to {\bf{0, A}} \to {\bf{1, B}} \to {\bf{BB, B}} \to {\bf{1}}\).

Hence, phase structure grammar for the language is:

\({\bf{S}} \to {\bf{00AB, A}} \to {\bf{AA, A}} \to {\bf{0, A}} \to {\bf{1, B}} \to {\bf{BB, B}} \to {\bf{1}}\).

Now, we shall find a phrase-structure grammar for part (c) languages.

Consider the following language:

\({\bf{L = }}\left\{ {{\bf{a: a is a bit string consisting of an even number of 1s followed by a final 0}}} \right\}\)

Then, the phrase structure grammar which generates the language L is:

\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\)

If\({\bf{V = }}\left( {{\bf{0, 1, S, A, B, C}}} \right){\bf{, T = }}\left\{ {{\bf{0,1}}} \right\}\), S is the starting symbol and the productions are:

\({\bf{S}} \to {\bf{A0}},{\bf{A}} \to {\bf{\lambda }},{\bf{A}} \to {\bf{BBC, A}} \to {\bf{BCB, A}} \to {\bf{CBB, C}} \to {\bf{CC, B}} \to {\bf{CB, B}} \to {\bf{BC, B}} \to {\bf{1, C}} \to {\bf{0}}\)

Hence phase structure grammar is:

\({\bf{S}} \to {\bf{A0}},{\bf{A}} \to {\bf{\lambda }},{\bf{A}} \to {\bf{BBC, A}} \to {\bf{BCB, A}} \to {\bf{CBB, C}} \to {\bf{CC, B}} \to {\bf{CB, B}} \to {\bf{BC, B}} \to {\bf{1, C}} \to {\bf{0}}\)

Now, we shall find a phrase-structure grammar for part (d) languages.

Consider the following language:

\({\bf{L = }}\left\{ {{\bf{a: a is a bit string that have neither two consecutive Os or two consecutive 1s}}} \right\}\)

Then, the phrase structure grammar which generates the language L is:

\({\bf{G = }}\left( {{\bf{V, T, S, P}}} \right)\)

If\({\bf{V = }}\left( {{\bf{0, 1, S, A, B}}} \right){\bf{, T = }}\left\{ {{\bf{0,1}}} \right\}\), S is the starting symbol and the productions are

\({\bf{S}} \to {\bf{A, A}} \to {\bf{AA, A}} \to {\bf{A0, A}} \to {\bf{01}}\), \({\bf{A}} \to {\bf{\lambda }}\), \({\bf{S}} \to {\bf{B, B}} \to {\bf{BB, B}} \to {\bf{B1, B}} \to {\bf{10}}\),\({\bf{B}} \to {\bf{\lambda }}\)

Hence phase structure grammar is:

\({\bf{S}} \to {\bf{A, A}} \to {\bf{AA, A}} \to {\bf{A0, A}} \to {\bf{01}}\),\({\bf{A}} \to {\bf{\lambda }}\),\({\bf{S}} \to {\bf{B, B}} \to {\bf{BB, B}} \to {\bf{B1, B}} \to {\bf{10}}\),\({\bf{B}} \to {\bf{\lambda }}\)