write a Java/C++/Python or other object-oriented program that reads a CFG and transform it into an equivalent CFG in Chomsky normal form.

Input: A context-free grammar (CFG) given by G = (V, , S, P).

Output: An equivalent CFG, G, written in Chomsky normal form such that L(G) = L(G).

E and P is a finite set of formulas of the form A a, where A E Vand a E (V US) The first phase of getting the equivalent Chomsky normal form is to eliminate the nullable variables of G. Here is a recursive definition of the set of nullable variables of G. If there is a production A- AthenA is nullable. If A, A2, Ak are nullable variables and there is a production B A1A2... Ak, then Bis nullable For every CFG G (V y, S, P) the following algorithm produces a CFG G1 V, y, S, P1) having no A-productions for which L(G1) L(G) -[At. The main algorithm to do that has the following steps: 1. Identify the nullable variables in Vand initialize P1 to P. 2. For every production A o in P, add to P1 every production obtained by deleting from one or more variable-occurrences involving a nullable variable 3. Delete every A production from P1, as well as every production of the form A A Example: If G (HS, Ah, la, b, ch, S, {S cs I aAb, A aAb IA), then the equivalent grammar having no A-productions is G' (IS, Ah, la, b, ch, S, IS cS l aAb l ab, A aAb I ab). The next phase of getting the equivalent Chomsky normal form is to eliminate unit productions This technique is similar to identifying the nullable variable described above. We first identify pairs of variables (A, B)for which A B (in this case we call B A-derivable); then for each such pair (A, B) and each nonunit production B ou, we add the production A o. Such pairs can be found as described in the below three steps: 1. If A B is a production, then B is A-derivable 2. f Cis A-derivable and C B is a production, then B is A-derivable 3. No other variables are A-derivable. To summarize, for every CFG G (V, J, S, P) without A-productions, the CFG G1 (V, J, S, P1) produced by the following algorithm generates the same language a G and has no unit productions: 1. Initialize P1 to P, and for each AEV identify the A-derivable variables 2. For every such pair A Band every non-unit production B a, add the production A to P1 E and P is a finite set of formulas of the form A a, where A E Vand a E (V US) The first phase of getting the equivalent Chomsky normal form is to eliminate the nullable variables of G. Here is a recursive definition of the set of nullable variables of G. If there is a production A- AthenA is nullable. If A, A2, Ak are nullable variables and there is a production B A1A2... Ak, then Bis nullable For every CFG G (V y, S, P) the following algorithm produces a CFG G1 V, y, S, P1) having no A-productions for which L(G1) L(G) -[At. The main algorithm to do that has the following steps: 1. Identify the nullable variables in Vand initialize P1 to P. 2. For every production A o in P, add to P1 every production obtained by deleting from one or more variable-occurrences involving a nullable variable 3. Delete every A production from P1, as well as every production of the form A A Example: If G (HS, Ah, la, b, ch, S, {S cs I aAb, A aAb IA), then the equivalent grammar having no A-productions is G' (IS, Ah, la, b, ch, S, IS cS l aAb l ab, A aAb I ab). The next phase of getting the equivalent Chomsky normal form is to eliminate unit productions This technique is similar to identifying the nullable variable described above. We first identify pairs of variables (A, B)for which A B (in this case we call B A-derivable); then for each such pair (A, B) and each nonunit production B ou, we add the production A o. Such pairs can be found as described in the below three steps: 1. If A B is a production, then B is A-derivable 2. f Cis A-derivable and C B is a production, then B is A-derivable 3. No other variables are A-derivable. To summarize, for every CFG G (V, J, S, P) without A-productions, the CFG G1 (V, J, S, P1) produced by the following algorithm generates the same language a G and has no unit productions: 1. Initialize P1 to P, and for each AEV identify the A-derivable variables 2. For every such pair A Band every non-unit production B a, add the production A to P1