4. This question develops your ability to convert a CFG into Chomsky Normal Form and to understand properties that result from that form. Consider the grammar G below.

A A+B|B B BC|C C (A)|5

(a) Convert G into a CFG in Chomsky Normal Form. So each rule has the form: A BC or A a.

(b) Show that if G is a CFG in Chomsky Normal Form, then for any string w L(G) of length n 1, exactly 2n 1 steps are required for any derivation of w.