The Gateway to Computer Science Excellence
+1 vote
656 views
S -> AB

A -> aBB | epsilon

B -> bAA | epsilon

What will be the CFG after removal of NULL production

My doubt is in this grammer epsilon is also accepted So we cant remove it right else the equivalent grammer will not be same as this grammer so What should be the answer of such problem if said to get rid of null productions?
in Theory of Computation by Loyal (6.9k points) | 656 views
+1

You can't remove null production from this grammar as this grammar is generating epsilon.

What should be the answer of such problem if said to get rid of null productions

Statement:- Null production can be removed from every CFG. -> FALSE 

Because if the epsilon is part of that language as a string then you can't remove that production from the grammar else that language will not the same one from which we have started.

0
Yes sir thats what i said so simply my answer would be that we cant remove it. Right?

1 Answer

0 votes

Null Production cannot be removed if it is generated from start symbol. For example a*

if you try to remove epsilon production it will be changed to a+

by Active (4.2k points)

Related questions

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
50,644 questions
56,516 answers
195,580 comments
101,143 users