1 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.

Show each step of the process and the final set of 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, e cannot appear on the right-hand side in CNF. Eo 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'. Y Z) or (X word). -> ...), d. A rule (XY) is not allowed in CNF; it must be (X Replace each rule of the form (XY) 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.