Q4Theory of Computation

A production $A\to ϵ$ is called null/nullable. First identify all nullable non-terminals: $A$ is nullable if $A\to ϵ$ directly, or if $A\to B_1{B}_2\cdots B_k$ where every $B_i$ is nullable. Then, for every production $A\to \alpha$ where $\alpha$ contains one or more nullable non-terminals, add new productions with every combination of nullable symbols omitted (excluding the case where everything is omitted, unless $A\to ϵ$ is otherwise needed to preserve the language, in which case it is retained only for the start symbol). Finally, delete all productions of the exact form $X\to ϵ$ (except possibly for the start symbol, if $ϵ\in L(G)$).

A production of the form $A\to B$, where both $A$ and $B$ are non-terminals, is a unit production. These are eliminated by computing, for each non-terminal $A$, the set of non-terminals reachable via a chain of unit productions, then replacing each unit production $A\to B$ with copies of all of $B$'s non-unit productions directly under $A$: i.e., if $B\to \gamma$ is a non-unit production, add $A\to \gamma$. This is repeated (or computed via transitive closure) until no unit productions remain.

Let $G$: $S\to AB$, $A\to a\mid ϵ$, $B\to b\mid A$. Step 1: $A$ is nullable (direct). Is $B$ nullable? $B\to A$ and $A$ is nullable, so $B$ is also nullable. Is $S$ nullable? $S\to AB$, both nullable, so $S$ is nullable too, but since $S$ is the start symbol we may retain $S\to ϵ$ only if required; here we proceed assuming $ϵ$ need not be specially preserved unless asked. Rewrite productions accounting for nullable symbols: from $S\to AB$, add $S\to A$ (omit B) and $S\to B$ (omit A); from $B\to A$, since $A$ is nullable, add $B\to ϵ$ but this is itself a null production so it is simply noted and then dropped after use. Remove all epsilon rules: $A\to ϵ$ and any newly introduced ones are deleted. Resulting grammar: $S\to AB\mid A\mid B$, $A\to a$, $B\to b\mid A$.

Step 2: eliminate unit productions $S\to A$, $S\to B$, and $B\to A$. For $S\to A$: $A$'s only non-unit production is $A\to a$, so add $S\to a$. For $S\to B$: $B$'s non-unit production is $B\to b$ (and $B\to A$ is itself a unit production, so trace further: $B\to A\to a$, giving $B\to a$ transitively), so add $S\to b$ and $S\to a$ (already present). For $B\to A$: add $B\to a$. After removing the unit productions themselves, the final simplified grammar is: $S\to AB\mid a\mid b$, $A\to a$, $B\to b\mid a$.

Removing null and unit productions (along with useless symbols — non-generating non-terminals that derive no terminal string, and unreachable symbols not derivable from the start symbol) is a mandatory preprocessing step before converting a CFG to Chomsky Normal Form, since CNF explicitly disallows both epsilon rules (except possibly at the start symbol) and single-non-terminal right-hand sides. It also produces a cleaner, more compact grammar, useful for both parser generation and for the formal proofs that rely on CNF-style structural bounds, such as the CFL pumping lemma and CYK parsing.