4.4 CNF, CFG, and PDA

Context-free grammars are a generative model: they describe how a start symbol can expand into sentences. A pushdown automaton (PDA) is a recognizer model: it reads an input stream while using an unbounded stack. The central theorem is that these models have the same expressive power:

The context-free languages are exactly the languages recognized by nondeterministic PDAs.

This does not mean that every production parser is literally a textbook PDA. It gives us a precise explanation for why a stack is enough for nested syntax and matching pairs, yet finite automata are not enough.

Chomsky normal form (CNF) is another formal tool. It restricts the shape of CFG productions so algorithms such as CYK parsing can reason about substrings systematically. CNF is primarily a proof and algorithmic normalization, not the grammar style you would normally hand to users or maintain directly in a compiler.

Chomsky Normal Form

A CFG is in CNF when every production has one of these forms:

A -> B C
A -> a

where A, B, and C are nonterminals and a is a terminal. A common controlled exception allows the start symbol to produce ε when the language includes the empty string.

CNF forbids:

• long right-hand sides such as A -> B C D;

• mixed rules such as A -> a B;

• unit productions such as A -> B;

• arbitrary epsilon productions.

Why accept such an awkward restriction? Because it makes every nonterminal derive either one terminal or exactly two smaller nonterminal spans. Dynamic-programming parsers can then fill a table by trying split points:

Does A derive tokens i through j?
Try every k between i and j.
Can A -> B C split as B derives i..k and C derives k+1..j?

That regular structure is what gives CYK a clear, though expensive, O(n^3 * |G|) style bound.

A Practical Conversion Pipeline

The exact order can vary, but a standard route is:

1. Add a fresh start symbol if the old start symbol appears on a right-hand side or if the construction needs a protected start.

2. Remove epsilon productions while preserving the language, with a controlled start-symbol exception when needed.

3. Remove unit productions such as A -> B.

4. Remove useless symbols: unreachable symbols and symbols that cannot derive terminals.

5. Replace terminals inside longer right-hand sides with helper nonterminals.

6. Break right-hand sides longer than two symbols into binary rules.

For example:

S -> A B C | b
A -> a A | ε
B -> C
C -> b

may become:

S   -> A X | B C | b
X   -> B C
A   -> X_a A | a
B   -> b
C   -> b
X_a -> a

The helper names are not language features. They are bookkeeping introduced by the transformation.

PDA: A Finite Controller Plus a Stack

A PDA extends a finite automaton with a stack. Conceptually, a transition can:

• inspect the next input symbol or choose an epsilon move;

• inspect the stack top;

• change state;

• push zero or more stack symbols;

• pop a stack symbol.

For balanced parentheses, a PDA can use this policy:

On "(" : push "("
On ")" : pop "("
At EOF : accept only when the stack contains just its bottom marker

The stack depth represents how many opening parentheses remain unmatched. That quantity can grow without bound, which is exactly the memory a finite automaton lacks.

For the language:

{ a^n b^n | n >= 0 }

the PDA pushes one marker for each a, then pops one marker for each b. It accepts only if the input changes from a to b in the correct direction and the stack empties exactly at the end.

This is still not enough for every language. A single stack cannot generally recognize:

{ a^n b^n c^n | n >= 0 }

because it would need to compare three unbounded counts in a way CFGs/PDA cannot express. This boundary matters when deciding what should be syntax, what should be a semantic constraint, and what may require a different formal model.

From Grammar to PDA, and Back Again

The equivalence theorem has useful construction intuition.

To build a PDA from a CFG:

1. Push the start symbol onto the stack.

2. When the stack top is a nonterminal, nondeterministically replace it with the right-hand side of one of its productions, pushed in reverse order.

3. When the stack top is a terminal matching the next input token, pop it and consume the input token.

4. Accept when the input is exhausted and the stack returns to its bottom marker.

The nondeterminism represents choosing a production before enough input may be known. Practical parsers tame that choice with lookahead, parse tables, parser states, or generalized parsing algorithms.

In the other direction, a PDA can be encoded as a CFG whose nonterminals describe state-and-stack relationships. That construction is more technical, but it establishes the theorem: CFGs and nondeterministic PDAs describe the same class of languages.

Deterministic and Nondeterministic PDA

Every deterministic PDA recognizes a context-free language, but not every context-free language has a deterministic PDA. This distinction is one reason real parser design is interesting. Languages intended for efficient deterministic parsing are often restricted or shaped so LL, LR, or related algorithms can make decisions predictably. A grammar may be context-free in theory yet awkward for a particular deterministic parser.

Use Each Formal Tool for Its Actual Job

CNF helps because one-token spans are base cases and longer spans split into two smaller spans. For id + id, a CYK-style parser can try each split point and ask which nonterminals cover the two pieces. That regular shape is useful for proofs and dynamic programming, not a reason to maintain human-facing grammars as CNF full of helper names.

Likewise, a PDA stack represents nested obligations: it can remember the most recent unmatched delimiter, but cannot generally compare three independent unbounded regions such as a^n b^n c^n. This boundary helps decide whether a rule is syntax or belongs in later semantic analysis.