Hogyan hozzam Chomsky normálformára a következő nyelvtant?

Eredeti helyettesítési szabályok:

S → BC | aA

A → ba | SA

B → bA | Cbab | ε

C → BC | BBB

ε-mentesítés:

U₁ = {B}

U₂ = {B,C}

U₃ = {S,B,C}

S' → S | ε

S → BC | aA | B | C

A → ba | SA

B → bA | Cbab | bab

C → BC | BBB | B | BB

Álterminálisok bevezetése a és b helyett:

S' → S | ε

S → BC | DA | B | C

A → ED | SA

B → EA | CEDE | EDE

C → BC | BBB | B | BB

D → a

E → b

Hosszredukció:

S' → S | ε

S → BC | DA | B | C

A → ED | SA

B → EA | CF | EG

C → BC | BH | B | BB

D → a

E → b

F → EG

G → DE

H → BB

Lánctalanítás:

U(B) = {S,C,S'}

U(C) = {S,S'}

S' → ε

S → BC | DA

A → ED | SA

B → EA | CF | EG

 S → EA | CF | EG

 C → EA | CF | EG

 S'→ EA | CF | EG

C → BC | BH | BB

 S → BC | BH | BB

 S'→ BC | BH | BB

D → a

E → b

F → EG

G → DE

H → BB

Összesítve:

S' → EA | CF | EG | BC | BH | BB | ε

S → EA | CF | EG | BC | BH | BB | DA

A → ED | SA

B → EA | CF | EG

C → BC | BH | BB | EA | CF | EG

D → a

E → b

F → EG

G → DE

H → BB