Type 2 — context-free languages (one stack)
Parent: chomsky-hierarchy
Add one stack to a finite automaton → a pushdown automaton. The stack gives nesting / recursion (last-in-first-out).
How a PDA recognizes aⁿbⁿ: push a marker for every a, pop one for every b, and accept iff the stack is empty at the end — the stack literally counts the as so it can match the bs.
- Grammar: context-free — productions
A → γ(a single nonterminal on the left). - Automaton: pushdown automaton (PDA). Normal forms: Chomsky / Greibach. Parsing: CYK in
O(n³). - Examples:
aⁿbⁿ; balanced parentheses (the Dyck language, incl. multiple bracket types); palindromesw wᴿ;{ aⁱbʲ : i ≠ j }; matched XML/HTML tags; arithmetic expressions with precedence; and most programming-language syntax — which is why grammars and parsers are context-free.
Grammar → derivation → parse tree
A CFG generates strings by rewriting from the start symbol. Take S → a S b | a b (this generates aⁿbⁿ). Derive aabb:
S ⇒ a S b ⇒ a (a b) b = aabb
The parse tree records that derivation (leaves, left to right, spell the string):
For real syntax the tree also encodes precedence — E → E+T | T, T → T*F | F, F → (E) | id parses id + id * id so that * sits below + (binds tighter). That structural nesting is exactly the "one stack" of a PDA made visible, and what a finite automaton can't produce.
Closure: closed under union, concatenation, star — but not under intersection or complement (aⁿbⁿcⁿ = aⁿbⁿc* ∩ a*bⁿcⁿ is the classic failure).
Pumping lemma (context-free)Long words split
w = uvxyzwithv,ypumpable together:uvⁱxyⁱzstays in the language for alli.
Consequence: aⁿbⁿcⁿ is not context-free — one stack tracks one nested count, not two independent ones → climb to a bounded tape.
Decidability: membership is decidable (parsing); but equivalence of two CFGs is undecidable — the first crack, well below Turing power.
One stack vs two — the jump is sudden
One stack = context-free. Two stacks = a full Turing machine (Type 0): two stacks simulate a tape — one holds everything left of the head, the other everything from the head rightward; moving the head is a pop from one, push onto the other. So climbing from Type 2 to the top can be a single extra stack — no gradual Type-1 step. (Same leap for a queue automaton, or a two-counter Minsky machine.) Adding memory structure jumps tiers, it doesn't ramp.