Editing Chomsky normal form (section)

===DEL: Eliminate ε-rules===

An ε-rule is a rule of the form 
:''A'' → ε, 
where ''A'' is not ''S''<sub>0</sub>, the grammar's start symbol.

To eliminate all rules of this form, first determine the set of all nonterminals that derive ε.
Hopcroft and Ullman (1979) call such nonterminals ''nullable'', and compute them as follows:
* If a rule ''A'' → ε exists, then ''A'' is nullable.
* If a rule ''A'' → ''X''<sub>1</sub> ... ''X''<sub>''n''</sub> exists, and every single ''X''<sub>''i''</sub> is nullable, then ''A'' is nullable, too.

Obtain an intermediate grammar by replacing each rule 
:''A'' → ''X''<sub>1</sub> ... ''X''<sub>''n''</sub> 
by all versions with some nullable ''X''<sub>''i''</sub> omitted.
By deleting in this grammar each ε-rule, unless its left-hand side is the start symbol, the transformed grammar is obtained.<ref name="Hopcroft.Ullman.1979"/>{{rp|90}}

For example, in the following grammar, with start symbol ''S''<sub>0</sub>,
: ''S''<sub>0</sub> → ''AbB'' | ''C''
: ''B'' → ''AA'' | ''AC''
: ''C'' → ''b'' | ''c''
: ''A'' → ''a'' | ε
the nonterminal ''A'', and hence also ''B'', is nullable, while neither ''C'' nor ''S''<sub>0</sub> is.
Hence the following intermediate grammar is obtained:<ref group=note>indicating a kept and omitted nonterminal ''N'' by ''{{color|#006000|N}}'' and ''{{color|#ffc0c0|<s>N</s>}}'', respectively</ref>
: ''S''<sub>0</sub> → ''{{color|#006000|A}}b{{color|#006000|B}}'' | ''{{color|#006000|A}}b{{color|#ffc0c0|<s>B</s>}}'' | ''{{color|#ffc0c0|<s>A</s>}}b{{color|#006000|B}}'' | ''{{color|#ffc0c0|<s>A</s>}}b{{color|#ffc0c0|<s>B</s>}}'' &nbsp; | &nbsp; ''C''
: ''B'' → ''{{color|#006000|AA}}'' | ''{{color|#ffc0c0|<s>A</s>}}{{color|#006000|A}}'' | ''{{color|#006000|A}}{{color|#ffc0c0|<s>A</s>}}'' | ''{{color|#ffc0c0|<s>A</s>}}ε{{color|#ffc0c0|<s>A</s>}}'' &nbsp; | &nbsp; ''{{color|#006000|A}}C'' | ''{{color|#ffc0c0|<s>A</s>}}C''
: ''C'' → ''b'' | ''c''
: ''A'' → ''a'' | ε
In this grammar, all ε-rules have been "[[inlining|inlined]] at the call site".<ref group=note>If the grammar had a rule ''S''<sub>0</sub> → ε, it could not be "inlined", since it had no "call sites". Therefore it could not be deleted in the next step.</ref>
In the next step, they can hence be deleted, yielding the grammar:
: ''S''<sub>0</sub> → ''AbB'' | ''Ab'' | ''bB'' | ''b'' &nbsp; | &nbsp; ''C''
: ''B'' → ''AA'' | ''A'' &nbsp; | &nbsp; ''AC'' | ''C''
: ''C'' → ''b'' | ''c''
: ''A'' → ''a''
This grammar produces the same language as the original example grammar, viz. {''ab'',''aba'',''abaa'',''abab'',''abac'',''abb'',''abc'',''b'',''ba'',''baa'',''bab'',''bac'',''bb'',''bc'',''c''}, but has no ε-rules.