2,865 views
1 votes
1 votes
State true/false

In CNF , S-> espilon and Start symbol can appear on RHS side of production.

2 Answers

3 votes
3 votes
$\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.
0 votes
0 votes
S -> epsilon, can be present in CNF, if the language is containing epsilon.

No, start symbol should not be present on RHS.

Explanation:::

First to convert cfg to CNF, we have to check first whether the start symbol is occurring on the RHS of the production.

If it is so, then include a production S' -> S, and S' would be the new start symbol, else if start symbol is not occuring on the RHS, leave it as it is.

Now, check whether the grammar is containing epsilon or not, if it is containing then include production ::: start symbol -> epsilon, and this production would not be removed.

And after this, perform removal of epsilon and unit productions and then conversion.
edited by

Related questions

0 votes
0 votes
0 answers
1
2 votes
2 votes
1 answer
3