Question bank — Chomsky Normal Form (CNF) — conversion

False. The special rule $S_0\to \epsilon$ is allowed precisely so CNF can generate $\epsilon$ when the language contains it; only that one start-symbol rule may be empty.

False. "Two variables" means two variable occurrences; $A\to AA$ is a perfectly legal CNF rule since both children are variables.

False. Any variable may go to a single terminal; that restriction only applies to $\epsilon$-rules, not terminal rules.

False. The START step keeps the start symbol off the right-hand side; it may still appear on the left of any two-variable rule. $S_0\to BC$ is fine.

True (for $n\ge 1$). Every internal node has exactly two children, so the tree is a binary tree with $n$ leaves (one per terminal) and $n-1$ internal branchings, powering the $O(n^3)$ CYK Algorithm.

False. BIN creates fresh variables inside long right-hand sides; if you then run DEL, nullable propagation can force you to re-binarize the patched rules, so the cleanup is not equivalent and may need redoing.

False. It can still have mixed rules like $A\to aB$ or long rules like $A\to BCD$; TERM and BIN are still required.

True for form — an unreachable variable in CNF shape breaks no CNF rule. But it's dead weight; Sipser's pipeline doesn't require removing it, though a tidy grammar would.

False. Non-start $\epsilon$-rules are outright forbidden in CNF; DEL exists to eliminate every one of them.

Error — $A$ is nullable only if every symbol on some right-hand side is nullable. Here $C$'s status is unknown; if $C$ is not nullable, $A$ is not nullable.

Error — you must add a rule for every subset of the nullable positions dropped: $A\to XYZ\mid YZ\mid XY\mid Y$. Dropping both $X$ and $Z$ (giving $A\to Y$) was forgotten.

Error — the empty-right-hand-side case is never added (it would recreate an $\epsilon$-rule). You add $A\to X$ and $A\to Y$ only.

Error — unit pairs use the transitive closure, and you copy the non-unit bodies of each reachable variable. You must copy $C$'s terminal/two-variable bodies into $A$, not add another unit rule $A\to C$.

Error — a standalone $A\to a$ is already legal CNF. TERM only isolates terminals that are mixed with other symbols in a longer rule; you just created an illegal unit rule $A\to T_a$.

Error — that splits the rule into two alternatives, changing the language. BIN must chain: $A\to B_1{X}_1$, $X_1\to B_2{X}_2$, $X_2\to B_3{B}_4$.

Error — running steps out of Sipser order (START→DEL→UNIT→TERM→BIN) can reintroduce unit-like rules after UNIT already ran. Follow the order so UNIT never has to run twice.

Error — after copying $B$'s non-unit bodies you must delete the unit rule $A\to B$; keeping it leaves an illegal rename in the grammar.

So the start symbol never appears on any right-hand side; then giving the start the special $\epsilon$-privilege can't tangle with other rules that mention it.

DEL and UNIT can only shrink or rename right-hand sides, while TERM and BIN only lengthen or relabel; doing the shrinkers first means the lengtheners never have to be redone.

A nullable symbol can independently be present or absent in a derivation, so every combination of "which nullable symbols vanished" is a genuine derivation that must be preserved.

Adding it would recreate exactly the $\epsilon$-rule DEL is trying to remove, defeating the step (except for the permitted $S_0\to \epsilon$).

A rule $A\to B$ replaces one variable by one variable — the parse tree gets a node with a single child, which breaks the required full-binary structure and never emits a symbol.

Exactly two children at every internal node fixes the node count at $2n-1$ for a length-$n$ string, giving the predictable binary tree that CYK Algorithm and the Pumping Lemma for CFLs rely on.

GNF (rule form $A\to a\alpha$) is tuned for building Pushdown Automata and guaranteeing a terminal per derivation step; CNF's binary-tree shape is what CYK and the CFL pumping lemma need, so each normal form serves a different job.

For each variable you copy the non-unit bodies of every variable it can reach through unit chains, so a densely connected unit graph fans many bodies into many variables.

In the single rule $S_0\to \epsilon$ on the fresh start symbol; DEL removes every other $\epsilon$-rule but preserves this one when $\epsilon$ is in the language.

It's a trivial self-unit rule; UNIT's closure includes the reflexive pair $(S,S)$ and the rule is simply dropped, since copying $S$'s bodies into $S$ adds nothing.

It adds $A\to BC\mid B\mid C$ (all non-empty subsets) but never $A\to \epsilon$; the fully-empty case is skipped.

No — it has no terminal to isolate (TERM skips it) and length two needs no splitting (BIN skips it). It's already in final CNF shape.

No — it's already a legal terminal rule; DEL, UNIT, TERM, and BIN all leave a standalone single-terminal rule untouched.

After START you get $S_0\to S$, $S\to \epsilon$; DEL makes $S_0$ nullable, so the final CNF is just $S_0\to \epsilon$, the one permitted empty rule.

BIN alone can't fix it because the terminal is illegal; this is why TERM must run first, turning it into $A\to T_{a}B$ (already length 2, so BIN then skips it).