Question

Construct phrase-structure grammars to generate each of these sets.

a) \(\left\{ {\left. {{{\bf{0}}^{\bf{n}}}} \right|{\bf{n}} \ge {\bf{0}}} \right\}\)

b) \(\left\{ {\left. {{{\bf{1}}^{\bf{n}}}{\bf{0}}} \right|{\bf{n}} \ge {\bf{0}}} \right\}\)

c) \(\left\{ {\left. {{{\left( {{\bf{000}}} \right)}^{\bf{n}}}} \right|{\bf{n}} \ge {\bf{0}}} \right\}\)

Short answer

a) The phase structure grammar is \(S \to SS,S \to 0,S \to {\rm{\lambda }}\).

b) The phase structure grammar is \(S \to A0,A \to AA,A \to {\rm{1,A}} \to {\rm{\lambda }}\).

c) The phase structure grammar is \(S \to SS,S \to 000,S \to {\rm{\lambda }}\).

Step-by-step solution

Let’s construct a phrase-structure grammar

Let\(G{\bf{ }} = {\bf{ }}\left( {{\rm{V, T, S, P}}} \right)\)be the phrase structure grammar that produces all signed decimal numbers. It consists of a sign, either + or -, a non-negative integer, and a decimal fraction, which can either be the empty string or a decimal point followed by a positive integer.

Construct phrase-structure grammars to generate \(\left\{ {\left. {{{\bf{0}}^{\bf{n}}}} \right|{\bf{n}} \ge {\bf{0}}} \right\}\).

a)

\(L = \left\{ {\left. {{0^n}} \right|n \ge 0} \right\}\).

Then, \(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\) is a phrase structure grammar which generates the language L if \(V{\bf{ }} = {\bf{ }}\left\{ {0,{\bf{ }}S} \right\},{\bf{ }}T{\bf{ }} = {\bf{ }}\left( 0 \right)\), S is the starting symbol and the productions are

Hence, the phase structure grammar for the set is \(S \to SS,S \to 0,S \to {\rm{\lambda }}\).

Construct phrase-structure grammars to generate \(\left\{ {{{\bf{1}}^{\bf{n}}}{\bf{0|n}} \ge {\bf{0}}} \right\}\). b)

\(L = \left\{ {\left. {{1^n}0} \right|n \ge 0} \right\}\)

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

Hence, the phase structure grammar for the set is \(S \to A0,A \to AA,A \to {\rm{1,A}} \to {\rm{\lambda }}\).

Construct phrase-structure grammars to generate \(\left\{ {\left. {{{\left( {{\bf{000}}} \right)}^{\bf{n}}}} \right|{\bf{n}} \ge {\bf{0}}} \right\}\). c)

\(L = \left\{ {\left. {{{\left( {000} \right)}^n}} \right|n \ge 0} \right\}\)

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

Hence, the phase structure grammar for the set is \(S \to SS,S \to 000,S \to {\rm{\lambda }}\).