0 votes 0 votes Eliminate ε productions, unit productions, useless symbols and then rewrite the resulting grammar in the Chomsky Normal Form (in that order) for the following two input grammars: S -> 0E0 | 1FF | ε E -> G F -> S | E G -> S | ε Theory of Computation theory-of-computation conjunctive-normal-form + – hem chandra joshi asked Apr 10, 2018 hem chandra joshi 1.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply ankitgupta.1729 commented Apr 10, 2018 i edited by ankitgupta.1729 Aug 6, 2018 reply Follow Share @hem chandra joshi , please check it .. After, eliminating ε-productions, unit production & useless symbols , grammar is :- S ---> 00 | 0S0 | 1SS | 1S | 1 | ε ( empty string is in the language , so it can't be eliminated) In CNF , it is :- S' ---> S | ε S ---> AA | AB | TC | TS' | 1 B ----> S'A C -----> S'S' A ------> 0 T ------->1 1 votes 1 votes meghna commented Aug 6, 2018 reply Follow Share in peterlinz, its mentioned that whenever grammar contains epsilon, we add a new variable S' as the start symbol, and add to the set of productions, S'->S/epsilon , so i think there will be more productions. 1 votes 1 votes ankitgupta.1729 commented Aug 6, 2018 reply Follow Share @meghna , Thank You :) ...I forgot this thing while writing it. If any other mistake is there then please tell me.. 0 votes 0 votes Please log in or register to add a comment.