text: Eliminate epsilon, unit and useless symbols and rewrite into CNF
  
  Problem
  
  Eliminate epsilon, unit and the useless symbols for the given grammar and rewrite it into CNF.
  
  S->0E0|1FF| ε
  
  E->G
  
  F->S|E
  
  G->S| ε
  
  Solution
  
  In the given grammar, we will first remove the null production. There are two null productions in the grammar, as given below −
  
  S ==> ε
  
  G ==> ε
  
  So, remove null production and rewrite all the other rules containing G by epsilon there, along with old productions. We do not remove S ==> epsilon as it is the start symbol.
  
  Remove G ==> epsilon, we get the following −
  
  S ==> 0E0 | 1FF | ε
  
  E ==> G | ε
  
  F ==> S | E
  
  G ==> S
  
  Now remove E ==> epsilon, we get the following −
  
  S ==> 0E0 | 1FF | 00 | ε
  
  E ==> G
  
  F ==> S | E | ε
  
  G ==> S
  
  Now remove F ==> epsilon, we get the following −
  
  S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
  
  E ==> G
  
  F ==> S | E
  
  G ==> S
  
  Now, we have to remove unit production, there is only one unit production E ==> G and G ==> S,
  
  By removing G ==> S, we get the following −
  
  S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
  
  E ==> S
  
  F ==> S | E
  
  Remove E ==> S, we get the following −
  
  S ==> 0S0 | 1FF | 00 | 1S | 1 | ε
  
  F ==> S
  
  Removing F ==> S, we get the following −
  
  S ==> 0S0 | 1SS | 00 | 1S | 1 | ε
  
  Now we have to convert it to Chomsky normal form (CNF). So, we do the following −
  
  Add production A ==> 0, B==>1, C ==> AS and D ==> BS,
  
  We get final grammar as follows −
  
  S ==> CA | DS | BB | AS | 1 | ε
  
  A ==> 0
  
  B ==> 1
  
  C ==> AS
  
  D ==> BS