Chomsky and Greibach normal forms

1. Safe order of grammar simplification?
   Stuck? Peek at 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.

   Read lesson 3.2.1

2. Do parse trees correspond one-to-one with leftmost derivations?
   Stuck? Peek at 3.1.1 Context-free grammars, derivations and parse trees

   • CFG: A → α, single variable on the left. CFL = L(G) for some CFG. Regular ⊂ CFL.
   • Leftmost / rightmost derivations; parse tree with yield = leaves left to right.
   • Trees ↔ leftmost derivations ↔ rightmost derivations (one-to-one per string).

   Read lesson 3.1.1

3. What are the two parts of an induction proof?
   Stuck? Peek at 0.2.3 Proof techniques

   • P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
   • Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
   • Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
   • One counterexample kills a “for all”. Examples never prove it.

   Read lesson 0.2.3

Algorithms love uniform input. If every rule had exactly the same shape, we could predict how long derivations are, bound the height of parse trees, and fill a table to test membership. Two standard shapes exist: Chomsky Normal Form (binary trees) and Greibach Normal Form (one terminal per step). GATE asks for their derivation lengths almost every time this topic appears.

In a grammar where every rule is either A → BC (two variables) or A → a (one terminal), how many derivation steps produce a string of length 4?

Prediction check

7. You need 4 terminal steps (A → a), and to have 4 variables you need 3 splitting steps (each A → BC adds one variable). 3 + 4 = 7 = 2·4 − 1.

Chomsky Normal Form

Every CFL (without ε) has a CNF grammar.

Converting to CNF

1. Simplify (ε, unit, useless).
2. For each terminal a in a body of length ≥ 2, add Xₐ → a and replace a by Xₐ.
3. Break long bodies: A → B₁B₂…Bₖ becomes A → B₁C₁, C₁ → B₂C₂, …, Cₖ₋₂ → Bₖ₋₁Bₖ.

Example: S → aSb | ab ⇒ Xa → a, Xb → b, S → XaSXb | XaXb ⇒ S → XaY | XaXb, Y → SXb.

Derivation length and tree height in CNF

For a string of length n ≥ 1: exactly 2n − 1 derivation steps (n − 1 binary steps + n terminal steps). The parse tree is a binary tree above the leaves, so a string of length n needs height at least ⌈log₂ n⌉ + 1; conversely a tree of height h yields a string of length at most 2^(h−1). That bound powers the CFL pumping lemma (Chapter 3.4).

Greibach Normal Form

Each step produces exactly one terminal, so a string of length n takes exactly n steps. GNF has no left recursion (A ⇒⁺ A…), and it is the shape a stack machine can simulate one input symbol per move — a preview of the next chapter.

Putting it together

• CNF: binary trees, 2n − 1 steps, height bounds yield length.
• GNF: one terminal per step, n steps.
• Every CFL (minus ε) has grammars in both forms.

CNF tree for length n:         n leaves (terminal steps)
                               n − 1 binary nodes (A → BC)
                               total 2n − 1 rule applications
     height h ⇒ |w| ≤ 2^(h−1)   ;   |w| = n ⇒ height ≥ ⌈log₂ n⌉ + 1

Grammar side complete. Now the machine side: a finite automaton plus a stack — the push-down automaton — which accepts exactly the context-free languages. Its natural ancestor is the GNF derivation you just saw.

1. NAT

   Steps in a CNF derivation of a string of length 15?

   Write your answer before opening the key.

2. NAT

   Steps in a GNF derivation of a string of length 15?

   Write your answer before opening the key.

3. MSQ

   Which rules are allowed in CNF?

   1. A → BC
   2. A → a
   3. A → aB
   4. A → B
4. MCQ

   A CNF parse tree has 9 leaves (all terminals). Number of internal nodes using A → BC rules?

   1. 8
   2. 9
   3. 17
   4. 4

• Chomsky Normal Form (CNF)
• Greibach Normal Form (GNF)
• 2n − 1 derivation steps
• binary parse tree height bound
• left recursion

1. CNF rule shapes?
   Reveal answer

   A → BC or A → a (plus S → ε if needed).
2. Derivation steps in CNF for length n?
   Reveal answer

   2n − 1
3. Derivation steps in GNF for length n?
   Reveal answer

   n
4. GNF rule shape?
   Reveal answer

   A → aα (a terminal then variables).