A PUSHDOWN AUTOMATON IS A FINITE AUTOMATON AUGMENTED WITH A STACK. Formally, a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F) Q finite set of STATES Σ INPUT alphabet Γ STACK alphabet — may differ from Σ, and usually does δ the TRANSITION FUNCTION δ : Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ* q₀ start state Z₀ the INITIAL STACK SYMBOL (bottom marker) F accepting states ── READING THE TRANSITION FUNCTION ───────────────────────── A MOVE DEPENDS ON THREE THINGS: the current state, the input symbol (or ε, meaning no input is consumed), AND THE SYMBOL ON TOP OF THE STACK. A move DOES THREE THINGS: changes state, consumes the input symbol (or not, if ε), and REPLACES THE TOP STACK SYMBOL WITH A STRING. δ(q, a, X) = { (p, γ) } means: in state q, reading a, with X on top — go to p, POP X and PUSH γ. THE THREE STACK OPERATIONS ARE ALL SPECIAL CASES OF THAT ONE RULE, which is worth stating because students often look for three separate mechanisms: γ = ε → POP (X removed, nothing pushed) γ = X → NO CHANGE (X removed and replaced) γ = YX → PUSH Y (X replaced by Y on top of X) THE OUTPUT IS A SET, so PDAs are NON-DETERMINISTIC by default. ── INSTANTANEOUS DESCRIPTION ─────────────────────────────── The complete configuration of a PDA is a triple (q, w, γ) current state, REMAINING input, and the ENTIRE stack contents with the top written leftmost. A move is written (q, aw, Xβ) ⊢ (p, w, γβ). ── TWO MODES OF ACCEPTANCE ───────────────────────────────── ACCEPTANCE BY FINAL STATE L(M) = { w : (q₀, w, Z₀) ⊢* (p, ε, γ) for some p ∈ F } — the input is exhausted and the machine is in an accepting state; the stack contents are irrelevant. ACCEPTANCE BY EMPTY STACK N(M) = { w : (q₀, w, Z₀) ⊢* (p, ε, ε) } — the input is exhausted and the stack is empty; the state is irrelevant, and F is not used at all. THE TWO MODES ARE EQUIVALENT IN POWER: for every PDA accepting by final state there is one accepting by empty stack recognising the same language, and vice versa. The constructions add one state and one new bottom marker to prevent the stack emptying accidentally. THE MODE IS THEREFORE A CONVENIENCE, chosen to make a particular machine simpler to write — and an exam answer should always say which mode it is using. ── A FULLY WORKED PDA: L = { aⁿbⁿ : n ≥ 0 } ──────────────── THE STRATEGY: push a marker for every a, pop one for every b. IF THEY RUN OUT TOGETHER, THE COUNTS MATCHED. States q₀ (reading a's) and q₁ (reading b's); stack alphabet { A, Z₀ }; acceptance by empty stack. δ(q₀, a, Z₀) = (q₀, A Z₀) push A, keep the marker δ(q₀, a, A) = (q₀, A A) push another A δ(q₀, b, A) = (q₁, ε) first b: pop δ(q₁, b, A) = (q₁, ε) keep popping δ(q₁, ε, Z₀) = (q₁, ε) pop the marker and accept TRACE FOR aaabbb, writing the stack top-first: STATE REMAINING STACK ACTION ────────────────────────────────────────── q₀ aaabbb Z₀ start q₀ aabbb A Z₀ read a, push A q₀ abbb A A Z₀ read a, push A q₀ bbb A A A Z₀ read a, push A q₁ bb A A Z₀ read b, pop q₁ b A Z₀ read b, pop q₁ ε Z₀ read b, pop q₁ ε (empty) ε-move, pop Z₀ ────────────────────────────────────────── ACCEPT THE STACK HEIGHT PEAKS AT EXACTLY n = 3, WHICH IS THE POINT: the machine has stored a count that no finite automaton could, and it did so with only two states. THE MEMORY IS IN THE STACK, NOT IN THE STATES. WHY aabb IS ACCEPTED AND aab IS NOT: for aab the machine reaches (q₁, ε, A Z₀) — input exhausted with an A still on the stack, so the stack never empties and the string is rejected. The unmatched a is literally still sitting there. ── A SECOND EXAMPLE: EVEN-LENGTH PALINDROMES ─────────────── L = { w wᴿ : w ∈ {a,b}* }. PUSH each symbol while in q₀; at some point GUESS that the midpoint has been reached and move to q₁ by an ε-transition; then POP and match each remaining symbol. δ(q₀, a, X) = (q₀, aX) push δ(q₀, b, X) = (q₀, bX) push δ(q₀, ε, X) = (q₁, X) GUESS the midpoint δ(q₁, a, a) = (q₁, ε) match and pop δ(q₁, b, b) = (q₁, ε) match and pop δ(q₁, ε, Z₀) = (q₁, ε) accept THE ε-TRANSITION IS AN IRREDUCIBLE GUESS. The machine cannot know where the middle is without reading the whole string first, so it tries every possible midpoint in parallel and accepts if any works. THIS IS WHERE NON-DETERMINISM IS DOING REAL WORK — and, as the next section shows, it is work no deterministic PDA can do.

── DETERMINISTIC PUSHDOWN AUTOMATA (DPDA) ────────────────── A PDA is DETERMINISTIC if, for every (q, a, X): 1. |δ(q, a, X)| ≤ 1 — at most one move, and 2. if δ(q, ε, X) is non-empty, then δ(q, a, X) must be EMPTY for every a — an ε-move and a reading move may never both be available. THE CRUCIAL RESULT, AND THE MOST IMPORTANT SINGLE FACT IN THIS TOPIC: DPDA ⊊ NPDA NON-DETERMINISM STRICTLY INCREASES THE POWER OF A PUSHDOWN AUTOMATON. THIS IS THE OPPOSITE OF THE FINITE AUTOMATON CASE, where subset construction showed NFA = DFA. The contrast is worth stating deliberately: FINITE AUTOMATA: non-determinism adds NOTHING PUSHDOWN AUTOMATA: non-determinism adds POWER TURING MACHINES: non-determinism adds nothing (in computability; the time cost is the P vs NP question) WHY THE SUBSET CONSTRUCTION FAILS HERE: tracking all possible states of an NFA required only a SET of states, which is finite. Tracking all possible configurations of an NPDA would require a set of STACKS, and there are infinitely many possible stacks — so the construction cannot be carried out. THE SEPARATING LANGUAGE: EVEN-LENGTH PALINDROMES { w wᴿ }. A non-deterministic PDA guesses the midpoint, as above. A DETERMINISTIC one cannot: with no marker, it has no way to know when to stop pushing and start popping, and committing to a wrong midpoint is unrecoverable because the pushed symbols have been consumed. NOTE THE CONTRAST WITH { w c wᴿ }, palindromes with an explicit centre marker c — THAT language IS deterministic, because the c tells the machine exactly when to switch. THE DIFFERENCE BETWEEN THE TWO LANGUAGES IS PRECISELY THE DIFFERENCE BETWEEN GUESSING AND KNOWING. DETERMINISTIC CONTEXT-FREE LANGUAGES (DCFL) are those accepted by a DPDA. THEY MATTER ENORMOUSLY IN PRACTICE: · every DCFL has an unambiguous grammar · DCFLs are exactly the languages parsable by a deterministic LR parser, so PROGRAMMING LANGUAGES ARE DESIGNED TO BE DCFLs — that is what makes efficient parsing possible · DCFLs are CLOSED UNDER COMPLEMENT, while general CFLs are not ── CLOSURE PROPERTIES OF CONTEXT-FREE LANGUAGES ──────────── CLOSED UNDER: UNION (S → S₁ | S₂) CONCATENATION (S → S₁S₂) KLEENE STAR (S → S₁S | ε) substitution, homomorphism, reversal INTERSECTION WITH A REGULAR LANGUAGE — proved by a product construction running the PDA and a DFA together, and a very useful proof tool NOT CLOSED UNDER: INTERSECTION — the classic witness: L₁ = { aⁿbⁿcᵐ } and L₂ = { aⁿbᵐcᵐ } are both context-free, but L₁ ∩ L₂ = { aⁿbⁿcⁿ }, WHICH IS NOT. COMPLEMENT — follows from the above, since closure under complement plus closure under union would give closure under intersection by De Morgan. DIFFERENCE THE ASYMMETRY WITH REGULAR LANGUAGES IS INSTRUCTIVE: regular languages are closed under everything, context-free languages are not. THE REASON IS THE SAME AS EVERYTHING ELSE IN THIS TOPIC — a PDA has ONE stack, and simulating two machines at once would need two. ── THE SUMMARY ───────────────────────────────────────────── FINITE AUTOMATON + a STACK = PUSHDOWN AUTOMATON REGULAR LANGUAGES + nesting = CONTEXT-FREE LANGUAGES THE STACK BUYS EXACTLY ONE THING: THE ABILITY TO MATCH NESTED PAIRS TO UNBOUNDED DEPTH. It does not buy the ability to compare three counts, or to replay a string forwards — because a stack is last-in-first-out and can be read only by destroying it. Every limitation of context-free languages traces back to that single sentence.