3. (25 point) Convert the following CFG into an equivalent CFG in Chomsky normal form 1, using the procedure given in Theorem 2.9 CFG stands for context free grammar 001 Show intermediate steps (as presented in Example 2.10) EXAMPLE 2.10 Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The series of grammars presented illus trates the steps in the conversion. Rules shown in bold have just been added. Rules shown in gray have just been removed 1. The original CFG G6 is shown on the left. The result of applying the first step to make a new start variable appears on the right. SASA| aB 2. Remove -rules + , shown on the left, and A- , shown on the right. SoS S-ASA aB |a Bb 3a. Remove unit rules S -> S, shown on the left, and So -+ S, shown on the right. A BIS A BIS 3b. Remove unit rules A - B and A -> S. Bb Convert the remaining rules into the proper form by adding additional vari- ables and rules. The final grammar in Chomsky normal form is equivalent to Ge (Actually the procedure given in Theorem 2.9 produces several variables Ui and several rules Ui -> a. We simplified the resulting grammar by using a single variable U and rule Ua.) A1 SA Ua