The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
60 views

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 | ε

asked in Theory of Computation by Active (4.5k points) | 60 views
+1
@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
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.
0
@meghna , Thank You :) ...I forgot this thing while writing it. If any other mistake is there then please tell me..

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,861 questions
47,532 answers
145,982 comments
62,293 users