The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
41 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.4k points) | 41 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 ---> AA | AB | TC | TS | 1 | ε

B ----> SA

C -----> SS

A ------> 0

T ------->1

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

35,535 questions
42,875 answers
121,904 comments
42,216 users