convert the context-free grammar G = , where

into a Chomsky normal form grammar G' = . At each stage, your answers should show the steps of the conversion, namely which rules are being removed and what rules are being added, if any.

A) Rewrite the productions of G as a list of individual productions rather than in the disjunctive notation used above, and for each of these productions, indicate whether it is of one of the forms allowed in Chomsky normal form.

B) State the new production added to the list to take account of the new start variable S' .

C) dentify any unallowed productions and list the productions added to replace these unallowed productions. Repeat these steps for any new unallowed productions added.

D) Identify and eliminate any unit productions, along with any new unit productions added in eliminating these.

E) Remove the remaining productions that are not in Chomsky normal form, and indicate the productions added to replace each removed production. Reuse variables introduced for terminal symbols. You may also reuse sequencing variables when removed productions have the same right hand sides.

IS, At T 10, 1 S OSO A A 1A1 IEI OS