THE THEOREM: A LANGUAGE IS GENERATED BY A CONTEXT-FREE GRAMMAR IF AND ONLY IF IT IS ACCEPTED BY A PUSHDOWN AUTOMATON. Both directions are CONSTRUCTIVE, so each is an algorithm. Together with the earlier results this completes the picture: CONTEXT-FREE GRAMMAR ≡ PUSHDOWN AUTOMATON (generator) (recogniser) exactly as REGULAR EXPRESSION ≡ FINITE AUTOMATON one level down. ── DIRECTION 1: CFG → PDA ────────────────────────────────── THE STANDARD CONSTRUCTION BUILDS A ONE-STATE PDA THAT ACCEPTS BY EMPTY STACK. THE IDEA — and it is worth stating before the mechanics: THE STACK HOLDS THE PART OF THE SENTENTIAL FORM NOT YET MATCHED AGAINST THE INPUT. The PDA simulates a LEFTMOST DERIVATION. At every moment the stack contains what the derivation still has to produce, top symbol first. THE CONSTRUCTION. Given G = (V, T, P, S), build M = ({q}, T, V ∪ T, δ, q, S, ∅) with: 1. FOR EACH PRODUCTION A → α: δ(q, ε, A) contains (q, α) — replace the variable on top of the stack with the right-hand side, consuming no input. THIS IS AN EXPANSION STEP, and it is where the non-determinism lives: several productions for A give several choices. 2. FOR EACH TERMINAL a ∈ T: δ(q, a, a) = (q, ε) — if the input symbol matches the terminal on top of the stack, consume both. THIS IS A MATCHING STEP. START with S on the stack; ACCEPT by empty stack. THE CORRESPONDENCE IS EXACT: THE STACK CONTENTS AT ANY POINT ARE PRECISELY THE UNMATCHED SUFFIX OF THE CURRENT SENTENTIAL FORM IN A LEFTMOST DERIVATION. ── A WORKED SIMULATION ───────────────────────────────────── Grammar: S → a S b | ε (generating aⁿbⁿ) Input: aabb STACK REMAINING ACTION ────────────────────────────────────────────── S aabb expand S → aSb a S b aabb match a S b abb expand S → aSb a S b b abb match a S b b bb expand S → ε b b bb match b b b match b (empty) ε ACCEPT ────────────────────────────────────────────── READ THE EXPANSION STEPS IN ORDER: S → aSb, S → aSb, S → ε. THAT IS EXACTLY THE LEFTMOST DERIVATION S ⇒ aSb ⇒ aaSbb ⇒ aabb. THE PDA HAS NOT MERELY ACCEPTED THE STRING — IT HAS RECONSTRUCTED THE DERIVATION, which is why a parser can output a parse tree rather than a yes/no answer. NOTE THE NON-DETERMINISM: at the third step the machine chose S → ε rather than S → aSb. A real parser must decide which, and that decision problem is precisely what LL and LR parsing tables solve. ── THE GREIBACH NORMAL FORM VARIANT ──────────────────────── If the grammar is first converted to GNF (A → aα), the construction becomes even tighter: δ(q, a, A) contains (q, α) for each production A → aα EVERY MOVE NOW CONSUMES EXACTLY ONE INPUT SYMBOL — there are no ε-moves at all, so the machine makes exactly |w| moves on input w. THIS IS WHY GREIBACH NORMAL FORM WAS INVENTED, as the earlier topic said: it makes this proof immediate.

── DIRECTION 2: PDA → CFG ────────────────────────────────── THE HARDER DIRECTION, and the construction is ingenious. Assume the PDA accepts by empty stack (if not, convert first) and that each move pushes at most two symbols. THE VARIABLES OF THE GRAMMAR ARE TRIPLES: [ q X p ] meaning "the PDA can go from state q to state p while REMOVING EXACTLY THE SYMBOL X from the stack, net, consuming some input along the way". THE PRODUCTIONS: · S → [ q₀ Z₀ p ] for every state p — start in q₀ with Z₀ on the stack and empty it, ending anywhere. · If δ(q, a, X) contains (r, ε), add [ q X r ] → a — one move pops X directly. · If δ(q, a, X) contains (r, Y₁Y₂…Yₖ), add [ q X p ] → a [ r Y₁ s₁ ][ s₁ Y₂ s₂ ]…[ s_{k−1} Yₖ p ] for EVERY choice of intermediate states s₁…s_{k−1} — removing X requires removing everything pushed in its place, and the intermediate states are unknown, so the construction ENUMERATES ALL POSSIBILITIES. THE COST IS SEVERE: the number of productions is exponential in the length of the pushed strings and polynomial in |Q|, which is why THIS DIRECTION IS A THEORETICAL RESULT AND NOT A PRACTICAL ALGORITHM. Nobody converts a real PDA to a grammar. THE IDEA THAT MAKES IT WORK, stated plainly: A STACK SYMBOL'S ENTIRE LIFETIME — from being pushed to being popped — IS A SELF-CONTAINED SUB-COMPUTATION, and that nesting of lifetimes is exactly the nesting of a derivation tree. THE STACK DISCIPLINE **IS** THE TREE STRUCTURE. ── THE COMPLETE CORRESPONDENCE ───────────────────────────── Collecting both levels of the hierarchy: REGULAR: regular expression ≡ DFA ≡ NFA ≡ regular grammar CONTEXT-FREE: context-free grammar ≡ (non-deterministic) PDA NOTE THE ASYMMETRY, which is the single most important observation here: AT THE REGULAR LEVEL, THE DETERMINISTIC AND NON-DETERMINISTIC MACHINES ARE EQUIVALENT. AT THE CONTEXT-FREE LEVEL, THEY ARE NOT — the equivalence is with the NON-DETERMINISTIC PDA only. CFG ≡ NPDA CFG ≢ DPDA — deterministic PDAs accept only the DETERMINISTIC context-free languages, a proper subset. SO "THE CONTEXT-FREE LANGUAGES" ARE INTRINSICALLY NON-DETERMINISTIC, and any grammar for an inherently ambiguous language cannot be parsed by a deterministic machine at all. ── WHAT THE EQUIVALENCE BUYS ─────────────────────────────── 1. PROOF FLEXIBILITY, exactly as at the regular level. Some closure properties are easy on grammars and awkward on machines: · UNION, CONCATENATION and STAR are trivial on grammars (S → S₁ | S₂, S → S₁S₂, S → S₁S | ε) and messy on PDAs. · INTERSECTION WITH A REGULAR LANGUAGE is easy on machines — run the PDA and a DFA in parallel, taking the product of their states while keeping the single stack — and has no natural grammar proof at all. THE FREEDOM TO MOVE BETWEEN THEM IS THE PRACTICAL VALUE OF THE THEOREM. 2. DECIDABILITY RESULTS. Because a CFG can be converted to CNF and CYK applied, these are DECIDABLE: · MEMBERSHIP — is w ∈ L(G)? O(n³) by CYK. · EMPTINESS — is L(G) = ∅? Check whether S is generating. · FINITENESS — is L(G) finite? Look for a cycle among the useful variables. 3. AND THE UNDECIDABLE ONES, which are the more instructive list: · IS L(G₁) = L(G₂)? UNDECIDABLE · IS L(G) = Σ*? UNDECIDABLE · IS L(G₁) ∩ L(G₂) = ∅? UNDECIDABLE · IS G AMBIGUOUS? UNDECIDABLE · IS L(G) INHERENTLY AMBIGUOUS? UNDECIDABLE · IS L(G) REGULAR? UNDECIDABLE COMPARE THE REGULAR LEVEL, WHERE ALL OF THESE WERE DECIDABLE. ADDING A STACK BOUGHT EXPRESSIVE POWER AND COST ANALYSABILITY — the same trade-off noted in the equivalence topic of the last section, now made concrete with a list. AND THE TREND CONTINUES: at the Turing machine level, even membership becomes undecidable.