A CONTEXT-FREE GRAMMAR IS IN GREIBACH NORMAL FORM IF EVERY PRODUCTION HAS THE SHAPE A → a α where a is a SINGLE TERMINAL and α is a (possibly empty) STRING OF VARIABLES. So every right-hand side begins with EXACTLY ONE terminal, followed only by variables — never by another terminal. A → a is permitted (α empty) A → aBC is permitted A → aBc is NOT — the terminal c may not appear A → BC is NOT — it does not begin with a terminal As with CNF, S → ε is permitted if ε ∈ L(G), provided S appears on no right-hand side. ── THE DEFINING CONSEQUENCE ──────────────────────────────── EVERY DERIVATION STEP PRODUCES EXACTLY ONE TERMINAL. Therefore a string of length n is derived in EXACTLY n STEPS — no more, no fewer. Compare CNF's 2n − 1. THREE THINGS FOLLOW IMMEDIATELY: 1. NO LEFT RECURSION IS POSSIBLE. A production A → Aα would have to begin with a variable, which the form forbids. THIS IS THE PROPERTY THAT MAKES TOP-DOWN PARSING SAFE, since recursive descent's failure mode is precisely a recursive call made without consuming input. 2. MEMBERSHIP IS DECIDABLE BY BOUNDED SEARCH. To test whether w with |w| = n is generated, explore derivations to depth exactly n. The search space is finite, so the procedure terminates. (CNF gives the same guarantee with bound 2n − 1; GNF's bound is tighter and the argument simpler.) 3. THE LEFTMOST DERIVATION MATCHES THE INPUT POSITION BY POSITION. After k steps, exactly k input symbols have been produced — which is why GNF is the natural form for proving the equivalence of context-free grammars and pushdown automata. ── WHY GNF PROVES CFG = PDA ──────────────────────────────── THE MAIN THEORETICAL USE, and the reason the form was invented. Given a GNF grammar, build a one-state pushdown automaton: · the STACK holds the string of variables still to be derived · start with S on the stack · to process input symbol a with variable A on top: pop A and push α, for each production A → aα · accept by empty stack THE CORRESPONDENCE IS EXACT: THE STACK CONTENTS ARE PRECISELY THE SENTENTIAL FORM'S REMAINING VARIABLES, AND EACH INPUT SYMBOL TRIGGERS EXACTLY ONE PRODUCTION. That one-to-one match between input symbols and derivation steps is what GNF was designed to supply, and it is why the proof is short in GNF and awkward in any other form. ── THE CONVERSION ALGORITHM ──────────────────────────────── START FROM CHOMSKY NORMAL FORM — the conversion assumes no ε-productions and no unit productions, which CNF already guarantees. STEP 1 — ORDER THE VARIABLES A₁, A₂, …, Aₙ arbitrarily. STEP 2 — ENSURE EVERY PRODUCTION Aᵢ → Aⱼα HAS j > i. Working through i = 1, 2, …, n: (a) For each production Aᵢ → Aⱼα with j < i, SUBSTITUTE every right-hand side of Aⱼ for Aⱼ. Repeat until every remaining variable-initial production has j ≥ i. (b) If Aᵢ → Aᵢα remains — IMMEDIATE LEFT RECURSION — eliminate it with a new variable Bᵢ: Aᵢ → Aᵢα₁ | … | Aᵢαₘ | β₁ | … | βₚ becomes Aᵢ → β₁ | … | βₚ | β₁Bᵢ | … | βₚBᵢ Bᵢ → α₁ | … | αₘ | α₁Bᵢ | … | αₘBᵢ THE IDEA: the original generates β followed by any number of α's; the replacement generates β first and then loops through the α's using Bᵢ, so the recursion has moved to the RIGHT. STEP 3 — WORK BACKWARDS FROM Aₙ. After step 2, Aₙ's productions all begin with a terminal (there is no Aⱼ with j > n). Substitute Aₙ's right-hand sides into every production beginning with Aₙ, then handle A_{n−1}, and so on down to A₁. EACH SUBSTITUTION PROPAGATES A LEADING TERMINAL ONE LEVEL DOWN. STEP 4 — FIX THE Bᵢ VARIABLES the same way, substituting to give each a leading terminal. STEP 5 — REPLACE ANY REMAINING TERMINAL that is not in the leading position by a new variable, as in CNF step 4. ── A WORKED CONVERSION ───────────────────────────────────── GIVEN (already in CNF): A₁ → A₂ A₃ A₂ → A₃ A₁ | b A₃ → A₁ A₂ | a STEP 2, i = 3: A₃ → A₁A₂ has j = 1 < 3, so substitute A₁: A₃ → A₂A₃A₂ | a Now A₃ → A₂A₃A₂ has j = 2 < 3, so substitute A₂: A₃ → A₃A₁A₃A₂ | bA₃A₂ | a IMMEDIATE LEFT RECURSION in A₃ → A₃A₁A₃A₂. Eliminate with B₃, where α = A₁A₃A₂ and the non-recursive parts are bA₃A₂ and a: A₃ → bA₃A₂ | a | bA₃A₂B₃ | aB₃ B₃ → A₁A₃A₂ | A₁A₃A₂B₃ STEP 3, working backwards. A₃'s productions now all start with a terminal (b or a). ✓ A₂ → A₃A₁ starts with A₃, so substitute: A₂ → bA₃A₂A₁ | aA₁ | bA₃A₂B₃A₁ | aB₃A₁ | b A₁ → A₂A₃ starts with A₂, so substitute A₂'s new right-hand sides: A₁ → bA₃A₂A₁A₃ | aA₁A₃ | bA₃A₂B₃A₁A₃ | aB₃A₁A₃ | bA₃ STEP 4 — B₃ → A₁A₃A₂ begins with A₁, so substitute A₁'s right-hand sides, each of which now begins with a terminal. EVERY PRODUCTION NOW BEGINS WITH A SINGLE TERMINAL FOLLOWED ONLY BY VARIABLES. ✓ THE OBSERVATION WORTH MAKING: THE GRAMMAR HAS GROWN CONSIDERABLY. GNF conversion is notorious for producing large grammars, since each substitution multiplies out the alternatives — which is why it is a theoretical tool rather than a practical one.

── CNF VERSUS GNF, THE FULL COMPARISON ───────────────────── CHOMSKY NF GREIBACH NF ──────────────────────────────────────────────────────── form A → BC or A → a A → aα, α ∈ V* RHS begins with a variable or a ALWAYS exactly one terminal TERMINAL derivation length exactly 2n − 1 EXACTLY n tree shape BINARY arbitrary branching left recursion POSSIBLE IMPOSSIBLE by construction main use CYK parsing; proving CFG ≡ PDA; the context-free top-down parsing pumping lemma conversion cost can blow up on typically LARGER ε-removal still what it controls the SHAPE of the the PROGRESS of the tree derivation ──────────────────────────────────────────────────────── THE LAST ROW IS THE ONE TO REMEMBER. CNF makes the tree binary so that substrings can be combined pairwise — a structural guarantee. GNF makes every step consume one symbol — a temporal guarantee. Each normal form was designed for a specific algorithm, and neither is "better". ── WHERE GNF MATTERS IN PRACTICE ─────────────────────────── 1. LEFT RECURSION ELIMINATION. The full GNF conversion is rarely performed, but STEP 2(b) — the immediate left recursion elimination — is used constantly, because recursive descent parsers cannot handle left-recursive grammars at all. E → E + T | T becomes E → T E′ E′ → + T E′ | ε THIS IS EXACTLY THE GNF STEP, applied selectively. 2. PROVING TERMINATION. Any parser working on a GNF grammar terminates, because each step consumes input and the input is finite. This is the cleanest termination argument available for top-down parsing. 3. THE PDA EQUIVALENCE, as above — the theoretical result that makes the whole pushdown automaton section work. 4. BOUNDING DERIVATION LENGTH in proofs about context-free languages. ── THE LIMITATION SHARED WITH CNF ────────────────────────── NEITHER NORMAL FORM PRESERVES THE PARSE TREE'S SHAPE, and neither removes ambiguity. Converting an ambiguous grammar yields an ambiguous grammar in normal form. NORMAL FORMS REGULARISE THE **SYNTAX OF THE PRODUCTIONS**, NOT THE **STRUCTURE OF THE LANGUAGE**. A defect that lies in the language — inherent ambiguity — survives every transformation, exactly as the previous topic said it must. ── THE PLACE OF BOTH FORMS ───────────────────────────────── Normal forms are the context-free analogue of the DFA minimisation of the last section: a canonical-ish representation that makes algorithms possible. BUT NOTE THE WEAKER GUARANTEE. The minimal DFA is UNIQUE, so DFA equivalence is decidable. CNF AND GNF ARE NOT UNIQUE — many grammars in normal form generate the same language — AND CONTEXT-FREE GRAMMAR EQUIVALENCE IS UNDECIDABLE. THE LOSS OF CANONICITY IS EXACTLY THE LOSS OF DECIDABILITY, and that correspondence is one of the most instructive patterns in the whole subject.