Question

4. Transform the grammar with productions

S → baAB,

A → bAB|λ,

B → BAa |A| λ

into CNF and GNF

 5. Convert the grammar

S → AB|aB,

A → abb|λ,

B → bbA

into CNF and GNF.

Answer 1

Following is the procedure to transform:-

1. We will remove λ-productions: –

Removing A → λ: S → baAA|baA|ba, A → bAB|bB, B → BAa|A|Ba.

Removing B → λ: S → baAA|baA|baA|ba, A → bAB|bB|bA|b, B → BAa|A|Ba|Aa|a.

2. We will remove unit-production:-

B → A: S → baAA|baA|ba, A → bAB|bB|bA|b, B → BAa|bAB|bB|bA|b|Ba|Aa|a.

3. Now convert the grammar into Chomsky normal form: –

a) We will introduce new variables S_a for each a ∈ T and S_b for each b ∈ T:

S → S_bS_aAA|S_bS_aA|S_bS_a,

A → S_bAB| S_bB| S_bA| S_b,

B → BAS_a|S_bAB|S_bB|S_bA|S_b|B|AS_a|S_a,

S_a → a,

S_b→ b.

b) Now we are introducing additional variables to get the first two productions into normal form and we get the final result

S → S_bU|S_bX |S_bS_a,

A → S_bY |S_bB|S_bA|S_b,

B → BZ|S_bY |S_bB|S_bA|S_b|BS_a|AS_a|S_a,

U → S_aV,

V → AA,

X →S_a A,

Y → AB,

Z → AS_a,

S_a → a,

S_b → b.

Answer 2

Production given are as follows :Converting the grammar into Chomsky normal form: \(-\) Introduce new variables \(\mathrm{S}_{\mathrm{a}}\) for each \(\mathrm{a} \in \mathrm{T}\) and \(\mathrm{S}_{\mathrm{b}}\) for each \(\mathrm{b} \in \mathrm{T}\) :

\(\mathrm{S} \rightarrow \mathrm{S}_{\mathrm{b}} \mathrm{S}_{\mathrm{a}} \mathrm{A} \mathrm{B}\left|\mathrm{S}_{\mathrm{b}} \mathrm{S}_{\mathrm{a}} \mathrm{B}\right| \mathrm{S}_{\mathrm{b}} \mathrm{S}_{\mathrm{a}} \mathrm{A} \mid \mathrm{S}_{\mathrm{b}} \mathrm{S}_{\mathrm{a}}\)

\(\mathrm{A} \rightarrow \mathrm{S}_{\mathrm{b}} \mathrm{AB}\left|\mathrm{S}_{\mathrm{b}} \mathrm{B}\right| \mathrm{S}_{\mathrm{b}} \mathrm{A} \mid \mathrm{S}_{\mathrm{b}}\)

\(\mathrm{B} \rightarrow \mathrm{BAS}_{\mathrm{a}}\left|\mathrm{S}_{\mathrm{b}} \mathrm{AB}\right| \mathrm{S}_{\mathrm{b}} \mathrm{B}\left|\mathrm{S}_{\mathrm{b}} \mathrm{A}\right| \mathrm{S}_{\mathrm{b}}\left|\mathrm{BS}_{\mathrm{a}}\right| \mathrm{AS}_{\mathrm{a}} \mid \mathrm{S}_{\mathrm{a}}\)

\(\mathrm{S}_{\mathrm{a}} \rightarrow \mathrm{a}\)

\(\mathrm{S}_{\mathrm{b}} \rightarrow \mathrm{b}\)

Introducing more variables to get the productions into normal form and the final result are as follows:

\(\mathrm{S} \rightarrow \mathrm{S}_{\mathrm{b}} \mathrm{U}\left|\mathrm{S}_{\mathrm{b}} \mathrm{X}\right| \mathrm{S}_{\mathrm{b}} \mathrm{Y} \mid \mathrm{S}_{\mathrm{b}} \mathrm{S}_{\mathrm{a}}\)

\(\mathrm{A} \rightarrow \mathrm{S}_{\mathrm{b}} \mathrm{V}\left|\mathrm{S}_{\mathrm{b}} \mathrm{B}\right| \mathrm{S}_{\mathrm{b}} \mathrm{A} \mid \mathrm{S}_{\mathrm{b}}\)

\(\mathrm{B} \rightarrow \mathrm{BZ}\left|\mathrm{S}_{\mathrm{b}} \mathrm{V}\right| \mathrm{S}_{\mathrm{b}} \mathrm{B}\left|\mathrm{S}_{\mathrm{b}} \mathrm{A}\right| \mathrm{S}_{\mathrm{b}}\left|\mathrm{BS}_{\mathrm{a}}\right| \mathrm{AS}_{\mathrm{a}} \mid \mathrm{S}_{\mathrm{a}}\)

\(\mathrm{U} \rightarrow \mathrm{S}_{\mathrm{a}} \mathrm{V}\)

\(\mathrm{V} \rightarrow \mathrm{AB}\)

\(\mathrm{X} \rightarrow \mathrm{S}_{\mathrm{a}} \mathrm{B}\)

\(\mathrm{Y} \rightarrow \mathrm{S}_{\mathrm{a}} \mathrm{A}\)

\(\mathrm{Z} \rightarrow \mathrm{AS}_{\mathrm{a}}\)

\(\mathrm{S}_{\mathrm{a}} \rightarrow \mathrm{a}\)

\(\mathrm{S}_{\mathrm{b}} \rightarrow \mathrm{b}\)

\(\mathrm{S} \rightarrow \mathrm{baAB}\)

\(\mathrm{A} \rightarrow \mathrm{bAB} \mid \lambda\)

\(\mathrm{B} \rightarrow \mathrm{BAa}|\mathrm{A}| \lambda\)

Removing the \(\lambda\) -productions:

First removing \(A \rightarrow \lambda:\)

\(\mathrm{S} \rightarrow \mathrm{baAB} \mid \mathrm{baB}\)

\(\mathrm{A} \rightarrow \mathrm{AB} \mid \mathrm{bB}\)

\(\mathrm{B} \rightarrow \mathrm{BAa}|\mathrm{A}| \lambda \mid \mathrm{Ba}\)

Then removing \(\mathrm{B} \rightarrow \lambda\)

\(\mathrm{S} \rightarrow \mathrm{baAB}|\mathrm{baB}| \mathrm{baA} \mid \mathrm{ba}\)

\(\mathrm{A} \rightarrow \mathrm{bAB}|\mathrm{bB}| \mathrm{bA} \mid \mathrm{b}\)

\(\mathrm{B} \rightarrow \mathrm{BAa}|\mathrm{A}| \mathrm{Ba}|\mathrm{Aa}| \mathrm{a}\)

Removing unit-production \(\mathrm{B} \rightarrow \mathrm{A}\) :

\(\mathrm{S} \rightarrow \mathrm{baAB}|\mathrm{baB}| \mathrm{baA} \mid \mathrm{ba}\)

\(\mathrm{A} \rightarrow \mathrm{bAB} / \mathrm{bB}|\mathrm{bA}| \mathrm{b}\)

\(\mathrm{B} \rightarrow \mathrm{BAa}|\mathrm{bAB}| \mathrm{bB}|\mathrm{bA}| \mathrm{b}|\mathrm{Ba}| \mathrm{Aa} \mid \mathrm{a}\)