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

In CNF , S-> espilon and Start symbol can appear on RHS side of production.
in Theory of Computation by Active (1.3k points) | 189 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 (35.4k points)
+1

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
50,650 questions
56,193 answers
193,988 comments
94,863 users