Question

Let V = {S, A, B, a, b} and T = {a, b}. Determine whether G = (V, T, S, P) is a type 0 grammar but not a type 1 grammar, a type 1 grammar but not a type 2 grammar, or a type 2 grammar but not a type 3 grammar if P, the set of productions, is

\(\begin{array}{*{20}{l}}{{\bf{a) S }} \to {\bf{ aAB, A }} \to {\bf{ Bb, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{b) S }} \to {\bf{ aA, A }} \to {\bf{ a, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{c) S }} \to {\bf{ABa, AB }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{d) S }} \to {\bf{ ABA, A }} \to {\bf{ aB, B }} \to {\bf{ ab}}{\bf{.}}}\\{{\bf{e) S }} \to {\bf{ bA, A }} \to {\bf{ B, B }} \to {\bf{ a}}{\bf{.}}}\\{{\bf{f ) S }} \to {\bf{ aA, aA }} \to {\bf{ B, B }} \to {\bf{ aA, A }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{g) S }} \to {\bf{ bA, A }} \to {\bf{ b, S }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{h) S }} \to {\bf{ AB, B }} \to {\bf{ aAb, aAb }} \to {\bf{ b}}{\bf{.}}}\\{{\bf{i) S }} \to {\bf{ aA, A }} \to {\bf{ bB, B }} \to {\bf{ b, B }} \to {\bf{ \lambda }}{\bf{.}}}\\{{\bf{j) S }} \to {\bf{ A, A }} \to {\bf{ B, B }} \to {\bf{ \lambda }}{\bf{.}}}\end{array}\)

Short answer

a) Type 2, not type 3

b) Type 3

c) Type 0, not type 1

d) Type 2, not type 3

e) Type 2, not type 3

f) Type 0, not type 1

g) Type 3

h) Type 0, not type 1

i) Type 2, not type 3

j) Type 2, not type 3

Step-by-step solution

Types of Phrase-Structure Grammars Phrase-structure grammars

(I)A type- 0 grammar has no restrictions on its production.

(II) A type-1 grammar can have productions of the form\({W_1} \to {W_2}\), where\({W_1} \to lAr\). and\({W_2} \to lWr\), where A is a non-terminal, I and r, are zero or more terminal or non-terminals and W is a non-empty string of terminal or non-terminals. It can also have the production Sàλ. as long as S does not appear on the right-hand side of any other production.

(III)A type- 2 grammar can have the productions only of the form\({W_1} \to {W_2}\), where \({W_1}\) is a single non-terminal.

(IV) A type- 3 grammar can have the productions only of the form \({W_1} \to {W_2}\) with \({W_1} = A\) and either \({W_2} = aB\) or \({W_2} = a\) where A and B are non-terminals and a is a terminal or with \({W_1} = S\) and\({W_2} = \lambda \).

Now, I shall determine whether \({\bf{G  =   }}\left( {{\bf{V, T, S, P}}} \right)\) is a type 0 grammar but not a type 1 grammar, a type 1 grammar but not a type 2 grammar, or a type 2 grammar but not a type 3 grammar if P.

Suppose \(G{\bf{ }} = {\bf{ }}\left( {V,{\bf{ }}T,{\bf{ }}S,{\bf{ }}P} \right)\) is a phrase structure grammar with P as the set of productions.

The objective is to determine the type of grammar G has in each of the set of productions p

(a) If\(P{\bf{ }} = {\bf{ }}\left\{ {S \to aAB,{\bf{ }}A{\bf{ }} \to {\bf{ }}Bb,{\bf{ }}B{\bf{ }} \to \lambda } \right\}\), here by the definition or type 2 and type 3 clears that G is a type of 2 not type 3.

Therefore, the G is a type-2 grammar but not a type-3grammar.

(b) If \(P{\bf{ }} = {\bf{ }}\left\{ {S \to aA,{\bf{ }}A{\bf{ }} \to {\bf{ }}a,{\bf{ }}A{\bf{ }} \to b} \right\}\), here A type- 3 grammar can have the productions only of the form \({W_1} \to {W_2}\) with \({W_1} = A\) and either \({W_2} = aB\) or \({W_2} = a\)

Hence, the G is a type-3 grammar.

(c) If\(P{\bf{ }} = {\bf{ }}\left\{ {S \to ABa,{\bf{ }}AB{\bf{ }} \to {\bf{ }}a} \right\}\), here A type- 0 grammar has no restrictions on its production. And A type-1 grammar can have productions of the form\({W_1} \to {W_2}\), where\({W_1} \to lAr\). and\({W_2} \to lWr\).

Accordingly, the G is a type -0 grammar but not type-1 grammar.

(d) If\(P{\bf{ }} = {\bf{ }}\left\{ {S \to ABA,{\bf{ }}A{\bf{ }} \to {\bf{ }}aB,{\bf{ }}B{\bf{ }} \to ab} \right\}\), here A type- 2 grammar can have the productions only of the form\({W_1} \to {W_2}\), where \({W_1}\) is a single non-terminal. And by A type- 3 grammar can have the productions only of the form \({W_1} \to {W_2}\) with \({W_1} = A\) and either \({W_2} = aB\) or\({W_2} = a\).

Thereafter, the G is a type -2 but not a type-3 grammar.

(e) if \(P{\bf{ }} = {\bf{ }}\left\{ {S \to bA,{\bf{ }}A{\bf{ }} \to {\bf{ }}B,{\bf{ }}B{\bf{ }} \to a} \right\}\),

Here A type- 2 grammar can have the productions only of the form\({W_1} \to {W_2}\), where \({W_1}\) is a single non-terminal. And by A type- 3 grammar can have the productions only of the form \({W_1} \to {W_2}\) with \({W_1} = A\) and either \({W_2} = aB\) or\({W_2} = a\).

Henceforth, the G is a type - 2 but not a type 3 grammar.

(f) If\(P{\bf{ }} = {\bf{ }}\left\{ {S \to aA,{\bf{ }}aA{\bf{ }} \to {\bf{ }}B,{\bf{ }}B{\bf{ }} \to aA,\,A \to B} \right\}\), here A type- 0 grammar has no restrictions on its production. And A type-1 grammar can have productions of the form\({W_1} \to {W_2}\), where\({W_1} \to lAr\) and\({W_2} \to lWr\).

So, the G is a type-0 but not a type-1 grammar.

(g) If\(P{\bf{ }} = {\bf{ }}\left\{ {S \to bA,{\bf{ }}A{\bf{ }} \to {\bf{ }}b,{\bf{ }}S \to \lambda } \right\}\), A type- 3 grammar can have the productions only of the form \({W_1} \to {W_2}\) with \({W_1} = A\) and either \({W_2} = aB\) or\({W_2} = a\).

Therefore, the G is a type-3 grammar.

(h) If \(P{\bf{ }} = {\bf{ }}\left\{ {S \to AB,{\bf{ }}B{\bf{ }} \to {\bf{ }}aAb,{\bf{ }}aAb{\bf{ }} \to b} \right\}\),

Hence, the G is a type-0 but not a type-1 grammar.

(i) If \(P{\bf{ }} = {\bf{ }}\left\{ {S \to aA,{\bf{ }}A{\bf{ }} \to {\bf{ }}bB,{\bf{ }}B{\bf{ }} \to b,\,B \to \lambda } \right\}\),

So, the G is a type-2 but not a type-3 grammar.

(j) If \(P{\bf{ }} = {\bf{ }}\left\{ {S \to A,{\bf{ }}A{\bf{ }} \to {\bf{ }}B,{\bf{ }}B{\bf{ }} \to \lambda } \right\}\),

Therefore, the G is a type-2 but not a type-3 grammar.