in Theory of Computation
1,262 views
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 | ε

in Theory of Computation
1.3k views

3 Comments

edited by
@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
1
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
1
@meghna , Thank You :) ...I forgot this thing while writing it. If any other mistake is there then please tell me..
0
0

Please log in or register to answer this question.

Related questions