3
$\begingroup$

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?

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

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. Now I understand it. Just checked epsilon-elimination algorithm, and it became clear. $\endgroup$ – Igor Konoplyanko Apr 22 '14 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.