removing epsilon-productions

Suppose a form has an optional middle name field. Rather than carry a special 'blank' marker around, you could instead print two versions of the form: one with the field and one without. Removing epsilon-productions does exactly this for a grammar: instead of letting a variable vanish at derivation time, you bake the 'present' and 'absent' choices directly into the other rules, so no rule ever needs to derive the empty string.

The procedure has two phases. First, find all nullable variables: a variable A is nullable if A can derive the empty string epsilon, either directly (A -> epsilon) or indirectly (A -> BC where both B and C are nullable). Second, for every rule, generate new versions that cover every way of dropping the nullable variables on its right-hand side. For example, if A is nullable and you have a rule S -> AbA, you add the versions where each A is present or omitted: S -> AbA | bA | Ab | b. Then delete all the A -> epsilon rules. The new grammar derives exactly the same non-empty strings without any epsilon-production.

There is one exception worth stating plainly: if the original language contains the empty string itself (the start symbol is nullable), you cannot remove that. The standard fix is to add a fresh start symbol S0 with the single rule S0 -> S | epsilon, keep S0 -> epsilon as the only allowed epsilon-production, and ensure S0 never appears on any right-hand side. Removing epsilon-productions is the first cleanup step toward Chomsky normal form, and it can multiply the number of rules — if k nullable variables appear in one rule, that rule can spawn up to 2^k versions, which is a real source of blowup.