# Chomsky normal form: epsilon rule

I have pretty simple question, but still can't find an answer just googling it.

I'm trying to understand Chomsky Normal Form (CNF). There are three production rules:

1. $A \to BC$
2. $A \to \alpha$
3. $S \to \epsilon$

First two I understand. But last one $\epsilon$ doesn't makes sense for me. Why do we need this rule? What is use of having this?

• Should be migrated to cs.stackexchange. – Yuval Filmus Apr 21 '14 at 23:32
• To answer the question, without this rule you cannot represent languages containing $\epsilon$. This is the only reason for allowing this rule. – Yuval Filmus Apr 21 '14 at 23:33

The last rule is necessary for languages containing $\epsilon$. A context-free grammar in which $S$ does not generate $\epsilon$ can be converted to Chomsky normal form without the rule $S \to \epsilon$. Conversely, simple induction shows that all other rules do not generate $\epsilon$, so this rule is needed for languages generating $\epsilon$.
The rule arises during the $\epsilon$-elimination step. For each non-terminal generating $\epsilon$, we "optionally" delete it from any production containing in in the right-hand side, and continue the process inductively (eliminating one non-terminal overtly generating $\epsilon$ may reveal that under generates $\epsilon$). Finally, it could happen that $\epsilon$ is pushed all the way to the starting symbol $S$; there is no way to eliminate it there.