The Gateway to Computer Science Excellence
+1 vote
State true/false

In CNF , S-> espilon and Start symbol can appear on RHS side of production.
in Theory of Computation by Active | 287 views

1 Answer

+1 vote
$\epsilon$ is allowed in CNF if and only if it is in the language.

$S \rightarrow aS | \epsilon$

If we tried to remove $\epsilon$ from this grammar we would lose the meaning of the grammar, as you can see the language consists $a^{n},n\geq0$. So it is not possible to remove $\epsilon$ from this grammar.

Now coming to the start symbol, most authors do not allow start symbol on the right hand side. So it's better in practice to remove start symbol from the RHS.
by Boss

Yes , Generally ,epsilon is not allowed in the CNF form of grammars but There is one exception in CNF :- If the language contains empty string then we have to make a new start symbol S' and write its production as

S' ---> S | ϵ

Source :-

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
52,221 questions
59,854 answers
118,096 users