In this exercise you will transform E₀ into Chomsky Normal Form (CNF). There are five steps: 

(a) Add a new start symbol, 

(b) Eliminate ϵ rules, 

(c) Eliminate multiple words on right-hand sides, 

(d) Eliminate rules of the form (X → Y), 

(e) Convert long right-hand sides into binary rules. 

a. The start symbol, S, can occur only on the left-hand side in CNF. Add a new rule of the form S' → S, using a new symbol S'. 

b. The empty string, ϵ cannot appear on the right-hand side in CNF. E₀ does not have any rules with ϵ, so this is not an issue. 

c. A word can appear on the right-hand side in a rule only of the form (X → word). Replace each rule of the form (X → . . .word . . . ) with (X → . . .W' . . . ) and (W' → word), using a new symbol W'. 

d. A rule (X → Y ) is not allowed in CNF; it must be (X → Y Z) or (X → word). Replace each rule of the form (X → Y ) with a set of rules of the form (X → . . . ), one for each rule (Y → . . . ), where (. . . ) indicates one or more symbols. 

e. Replace each rule of the form (X → Y Z . . . ) with two rules, (X → Y Z') and (Z' → Z . . . ), where Z' is a new symbol.

Show each step of the process and the final set of rules.