Chapter recap
Clean a grammar in the order ε-productions → unit productions → useless symbols (non-generating first, then unreachable). CNF: A → BC | a; a length-n string takes 2n − 1 steps; height h bounds the yield by 2^(h−1). GNF: A → aα; n steps.
Merged rule card
From 3.2.1 Removing useless symbols, ε- and unit productions
- Useful = generating + reachable. Remove non-generating first, then unreachable.
- Nullable: A ⇒* ε. Add all versions dropping nullable occurrences; delete ε-rules; add S₀ → S | ε if needed.
- Unit pairs by reachability over unit rules; copy non-unit bodies; delete unit rules.
- Order: ε → unit → useless.
From 3.2.2 Chomsky and Greibach normal forms
- CNF: A → BC | a (+ S → ε). Length n ⇒ 2n − 1 steps; n − 1 binary nodes. Height h ⇒ |w| ≤ 2^(h−1).
- Conversion: simplify, replace terminals in long bodies, split long bodies.
- GNF: A → aα. Length n ⇒ n steps. No left recursion.
Practice questions
- NAT
CNF derivation steps for length 8?
Write your answer before opening the key.
- MCQ
S → AB, A → a, B → BB is cleaned. What remains?
- S → AB, A → a
- nothing — L = ∅
- A → a only
- S → a
- MSQ
Which are in GNF?
- A → aBC
- A → a
- A → BC
- A → aBb
- NAT
Nullable variables in S → AB | b, A → aA | ε, B → A | b?
Write your answer before opening the key.
- MCQ
A unit-pair computation finds A ⇒* C via unit rules and C → ab. What is added?
- A → C
- A → ab
- C → A
- nothing
- NAT
Max yield length of a CNF parse tree whose binary part has height 6?
Write your answer before opening the key.
Answer key
Reveal answers when you’re ready
- 15 — 2n − 1.
- B — B never generates (B → BB only), so S is non-generating: L = ∅.
- A: B is non-generating.
- C: A is unreachable once S goes.
- D: No such rule.
- AB — Terminal first, then only variables.
- C: No leading terminal.
- D: Terminal after variables.
- 3 — A (ε), B (→ A), S (→ AB).
- B — Copy C’s non-unit bodies to A.
- A: Unit rules are removed.
- C: Wrong direction.
- D: The body must be copied.
- 64 — 2⁶.