Chapter 23 of 34

Pushdown Automata

A finite automaton has a fixed, finite memory: its current state. That is exactly why it cannot recognise { anbn : n ≥ 1 }. To check that the number of b's equals the number of a's, it would have to remember an unbounded count, and a DFA with k states can only tell apart k different situations.

A pushdown automaton (PDA) fixes this by adding one simple, unlimited memory: a stack. Think of a pile of plates. You can put a plate on top (push), take the top plate off (pop), and look at the top plate, but you cannot reach the middle of the pile. With that alone, a PDA can push one symbol for every a and pop one for every b, and accept if the two cancel out exactly.

A pushdown automaton is a finite automaton equipped with a stack. In each move it reads one input symbol or nothing (ε), looks at and removes the top stack symbol, changes state, and pushes a string of stack symbols. Nondeterministic PDAs accept exactly the context-free languages.

In this chapter we will define PDAs formally, trace them with instantaneous descriptions, compare the two acceptance modes, design PDAs for standard languages, and see why deterministic PDAs are strictly weaker than nondeterministic ones. Every PDA in this chapter was run by a simulator on all strings up to length 9 or 12 and compared with the definition of its language.


Formal Definition

P = (Q, Σ, Γ, δ, q0, Z0, F)

Q    finite set of states
Σ    input alphabet
Γ    stack alphabet (may include input symbols)
δ    transition function   δ : Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ*
q0   start state
Z0   initial stack symbol (the stack starts holding just Z0)
F    set of final (accepting) states, F ⊆ Q

A transition (p, γ) ∈ δ(q, a, X) means:

"In state q, reading a (or reading nothing, if a = ε), with X on top of the stack: go to state p, pop X, and push the string γ."

We write γ with its leftmost symbol on top. So the three basic stack operations are all special cases of "pop X, push γ":

Effect

Transition

Stack before → after (top on the left)

Push a

δ(q, a, X) ∋ (p, aX)

X… → aX…

Pop

δ(q, b, X) ∋ (p, ε)

X… → …

No change

δ(q, c, X) ∋ (p, X)

X… → X…

Replace top

δ(q, c, X) ∋ (p, Y)

X… → Y…

In diagrams an arrow from q to p is labelled a, X / γ: "read a, pop X, push γ". Two important points:

  • Every move needs a top symbol. If the stack is empty, the PDA cannot move at all.

  • By default a PDA is nondeterministic: δ returns a set, and ε-moves may compete with reading moves. The PDA accepts if some sequence of choices leads to acceptance.


Instantaneous Descriptions

To trace a PDA we need its state, the input still unread, and the whole stack. This triple is an instantaneous description (ID):

(q, w, γ)      q = current state, w = remaining input, γ = stack (top on the left)

If (p, β) ∈ δ(q, a, X), then (q, aw, Xα) ⊢ (p, w, βα). We write ⊢* for zero or more moves.

Example: a PDA for { anbn : n ≥ 1 }

Idea: in q0 push an a for every a read. On the first b, switch to q1 and pop one a per b. When the original Z0 is on top again and the input is finished, move to the final state q2.

#

Transition

Meaning

1

δ(q0, a, Z0) = {(q0, aZ0)}

First a: push

2

δ(q0, a, a) = {(q0, aa)}

More a's: push

3

δ(q0, b, a) = {(q1, ε)}

First b: pop, start matching

4

δ(q1, b, a) = {(q1, ε)}

More b's: pop

5

δ(q1, ε, Z0) = {(q2, Z0)}

All a's matched: go to final state

F = {q2}. All other δ entries are empty.

     a, Z0 / aZ0
     a, a  / aa                 b, a / ε
       ┌──┐                       ┌──┐
       ▼  │                       ▼  │
 ──► ( q0 ) ───── b, a / ε ────► ( q1 ) ───── ε, Z0 / Z0 ────► (( q2 ))

Trace on aabb (accepted):

(q0, aabb, Z0) ⊢ (q0, abb, aZ0)      rule 1
               ⊢ (q0, bb, aaZ0)      rule 2
               ⊢ (q1, b, aZ0)        rule 3
               ⊢ (q1, ε, Z0)         rule 4
               ⊢ (q2, ε, Z0)         rule 5   input used up, final state → accept

Rejections:

  • aab: we reach (q1, ε, aZ0). No move is possible (rule 5 needs Z0 on top), and q1 is not final. Too many a's.

  • abb: we reach (q1, b, Z0). Rule 5 moves to (q2, b, Z0), but q2 has no moves and the input is not finished. Too many b's.

  • abab: after ab we are in (q1, ab, Z0). There is no move on a in q1, and the ε-move leads to q2 with input left over. An a after a b is never allowed.


Two Ways to Accept

Acceptance by final state: L(P) = { w : (q0, w, Z0) ⊢* (q, ε, α) for some q ∈ F and any stack α }.
Acceptance by empty stack: N(P) = { w : (q0, w, Z0) ⊢* (q, ε, ε) for any state q }.

In both cases the whole input must be read. For empty-stack acceptance, F is irrelevant (often written F = ∅).

To make the anbn PDA accept by empty stack, just change rule 5 to pop Z0: δ(q1, ε, Z0) = {(q1, ε)}. Trace on aaabbb:

(q0, aaabbb, Z0) ⊢ (q0, aabbb, aZ0) ⊢ (q0, abbb, aaZ0) ⊢ (q0, bbb, aaaZ0)
                 ⊢ (q1, bb, aaZ0)  ⊢ (q1, b, aZ0)     ⊢ (q1, ε, Z0)
                 ⊢ (q1, ε, ε)                         stack empty → accept

The two modes are equally powerful (for NPDAs)

Empty stack → final state. Given PN, build PF with a new start state p0, a new bottom marker X0 and a new final state pf:

  • δ(p0, ε, X0) = {(q0, Z0X0)}: put PN's stack on top of X0 and start PN.

  • For every state q of PN: δ(q, ε, X0) ∋ (pf, ε). Seeing X0 means PN has emptied its own stack, so jump to the final state.

Final state → empty stack. Given PF, build PN with a new start p0, bottom marker X0 and a new "draining" state p:

  • δ(p0, ε, X0) = {(q0, Z0X0)}.

  • For every final state q and every stack symbol X (including X0): δ(q, ε, X) ∋ (p, ε).

  • For every stack symbol X: δ(p, ε, X) ∋ (p, ε). State p pops everything.

Why X0? Without it, PF might empty its stack in a non-final state and PN would wrongly accept. X0 can only be removed in the draining state p, which is entered only from a final state.


Designing PDAs: Solved Problems

The general strategy is: use the stack to remember what still needs to be matched, use states to remember which phase you are in, and use Z0 to detect "everything matched".

Problem 1: { wcwR : w ∈ {a, b}* }

The middle marker c tells us exactly when to switch from pushing to popping.

δ(q0, x, X) = {(q0, xX)}     for x ∈ {a, b}, X ∈ {a, b, Z0}    push the first half
δ(q0, c, X) = {(q1, X)}      for X ∈ {a, b, Z0}                saw the middle
δ(q1, a, a) = {(q1, ε)}                                        match
δ(q1, b, b) = {(q1, ε)}                                        match
δ(q1, ε, Z0) = {(q2, Z0)}                                      F = {q2}
(q0, abcba, Z0) ⊢ (q0, bcba, aZ0) ⊢ (q0, cba, baZ0) ⊢ (q1, ba, baZ0)
                ⊢ (q1, a, aZ0)   ⊢ (q1, ε, Z0)     ⊢ (q2, ε, Z0)       accept

At every ID there is at most one possible move, so this PDA is deterministic.

Problem 2: { wwR : w ∈ {a, b}* } (even-length palindromes)

Now there is no middle marker. The PDA must guess where the middle is. We take the PDA above, delete the c-moves, and add an ε-move "the middle is here":

δ(q0, x, X) = {(q0, xX)}     for x ∈ {a, b}, X ∈ {a, b, Z0}
δ(q0, ε, X) = {(q1, X)}      for X ∈ {a, b, Z0}      guess: middle reached
δ(q1, a, a) = {(q1, ε)},  δ(q1, b, b) = {(q1, ε)}
δ(q1, ε, Z0) = {(q2, Z0)}                                F = {q2}

On abba, one branch guesses after "ab":

(q0, abba, Z0) ⊢ (q0, bba, aZ0) ⊢ (q0, ba, baZ0) ⊢ (q1, ba, baZ0)     guess
               ⊢ (q1, a, aZ0)   ⊢ (q1, ε, Z0)    ⊢ (q2, ε, Z0)        accept

Branches that guess at the wrong point simply get stuck. Since one branch accepts, abba is accepted. In state q0 with a on top and input b, both "push" and "guess middle" are possible: this PDA is nondeterministic, and as we will see, no deterministic PDA can accept this language.

Problem 3: { w ∈ {a, b}* : #a(w) = #b(w) }

The a's and b's can come in any order. Keep the excess on the stack: if a's are ahead, the stack holds that many a's; if b's are ahead, that many b's. A matching symbol cancels one. State q0 (final) means "counts equal", q1 means "something is on the stack".

Transition

Meaning

δ(q0, a, Z0) = {(q1, aZ0)}, δ(q0, b, Z0) = {(q1, bZ0)}

Counts were equal; now one is ahead

δ(q1, a, a) = {(q1, aa)}, δ(q1, b, b) = {(q1, bb)}

Excess grows

δ(q1, a, b) = {(q1, ε)}, δ(q1, b, a) = {(q1, ε)}

Cancel one

δ(q1, ε, Z0) = {(q0, Z0)}

Excess is zero again

(q0, abba, Z0) ⊢ (q1, bba, aZ0) ⊢ (q1, ba, Z0) ⊢ (q0, ba, Z0)
               ⊢ (q1, a, bZ0)   ⊢ (q1, ε, Z0) ⊢ (q0, ε, Z0)          accept (F = {q0})

A simulator accepted exactly the 1275 balanced strings among all strings of length ≤ 12. This PDA is also deterministic: in q1 with Z0 on top, the ε-move is the only move.

Problem 4: { anb2n : n ≥ 1 }

Push two symbols for each a, pop one for each b. Change rules 1 and 2 of the anbn PDA to δ(q0, a, Z0) = {(q0, aaZ0)} and δ(q0, a, a) = {(q0, aaa)}; keep rules 3, 4 and 5.

(q0, aabbbb, Z0) ⊢ (q0, abbbb, aaZ0) ⊢ (q0, bbbb, aaaaZ0) ⊢ (q1, bbb, aaaZ0)
                 ⊢ (q1, bb, aaZ0)    ⊢ (q1, b, aZ0)       ⊢ (q1, ε, Z0) ⊢ (q2, ε, Z0)

For { a2nbn } you would do the opposite: push one symbol for every two a's (using two states to count a's in pairs), or push one per a and pop two per b.

Problem 5: { aibjck : i = j or j = k }

A single stack cannot check both equalities at once, but it does not have to. At the start, the PDA guesses which condition holds:

  • Branch i = j: push a's, pop one per b, check Z0 is on top, then read any number of c's.

  • Branch j = k: read a's without pushing, push b's, pop one per c, check Z0.

The PDA accepts if either branch accepts. An 8-state version of this design was simulated on all strings over {a, b, c} up to length 9 with no errors. This language is a standard example of an inherently ambiguous CFL, and it has no DPDA.


Deterministic PDAs (DPDA)

A PDA is deterministic if, for every state q, input symbol a and stack symbol X: (1) δ(q, a, X) has at most one element, (2) δ(q, ε, X) has at most one element, and (3) if δ(q, ε, X) is non-empty then δ(q, b, X) is empty for every input symbol b.

Condition (3) is the subtle one: an ε-move is allowed, but only if it never competes with a reading move for the same state and top symbol. Our PDAs for anbn, wcwR and #a = #b satisfy all three conditions. The wwR PDA violates (3): δ(q0, ε, a) and δ(q0, a, a) are both non-empty.

Languages accepted by DPDAs (by final state) are the deterministic context-free languages (DCFLs). Key facts:

  • Regular ⊂ DCFL ⊂ CFL, both inclusions proper. Every DFA is a DPDA that ignores its stack. { anbn } is a DCFL but not regular. { wwR } is a CFL but not a DCFL: intuitively, a deterministic machine cannot know where the middle is, and after reading a long prefix it can never safely throw away the pushed symbols.

  • NPDAs are strictly more powerful than DPDAs. This is different from finite automata, where NFA and DFA are equivalent.

  • Every DCFL has an unambiguous grammar. The converse fails: wwR has an unambiguous grammar (S → aSa | bSb | ε) but is not a DCFL.

  • For DPDAs, the two acceptance modes are not equal. A DPDA accepting by empty stack can only accept languages with the prefix property (no string in L is a proper prefix of another string in L), because once the stack is empty the machine cannot move again. For example { an : n ≥ 0 } is regular, hence a DCFL, but no DPDA accepts it by empty stack.

  • DCFLs are exactly the languages of LR(1) grammars, which is why deterministic parsers in compilers handle them in linear time.


Finite Automata vs PDA vs Turing Machine

Feature

DFA / NFA

PDA

Turing machine

Extra memory

None

One stack (LIFO, unbounded)

Infinite tape, read and write anywhere

Input head

Left to right, read only

Left to right, read only (may pause with ε-moves)

Moves both ways, can write

Languages

Regular

Context-free

Recursively enumerable

Deterministic = nondeterministic?

Yes

No (DPDA weaker)

Yes

Example it can do

(ab)*

anbn, wwR

anbncn, ww

Adding a second stack makes a PDA as powerful as a Turing machine: two stacks can simulate a tape (the part left of the head on one stack, the part right of it on the other). That is covered with the other machine models in Variants of Turing Machines.


Common Mistakes

  • Forgetting that every move pops. To "just look" at the top X, push it back: (p, X). To push a on top of X, push aX, not just a.

  • Writing the pushed string in the wrong order. In (p, aZ0), a is the new top.

  • Accepting before the input ends. Reaching a final state or an empty stack counts only when all input is consumed.

  • Losing Z0 by accident. If you pop Z0 in a final-state PDA, the machine stops for good. Use Z0 as the "counter is zero" signal and push it back.

  • Calling a PDA deterministic just because each δ entry has one element. Check condition (3) as well: an ε-move and a reading move for the same (q, X) break determinism.

  • Assuming NPDA = DPDA because NFA = DFA. It is false for PDAs.


Practice and GATE-Style Questions

Q1. Which of these languages can be accepted by a DPDA? (i) { anbn : n ≥ 0 } (ii) { wcwR } (iii) { wwR } (iv) { anbm : n ≠ m }

(i), (ii) and (iv) are DCFLs. For (iv), push a's and pop one per b. Accept (final state) if the input ends while a's are still on the stack, or if a b arrives when only Z0 is left (more b's than a's). To keep it deterministic, push a special symbol A for the first a; then after each pop the state can record whether a's remain (popped a) or not (popped A). A simulator confirmed such a 5-state DPDA on all strings up to length 12. (iii) needs to guess the middle and is not a DCFL.

Q2. Write the sequence of IDs of the anb2n PDA on aabbb. Is it accepted?

(q0, aabbb, Z0) ⊢ (q0, abbb, aaZ0) ⊢ (q0, bbb, aaaaZ0)
                ⊢ (q1, bb, aaaZ0)  ⊢ (q1, b, aaZ0) ⊢ (q1, ε, aZ0)

No move is possible from (q1, ε, aZ0) and q1 is not final: rejected (one b short).

Q3. Design a PDA for { anbmcn : n, m ≥ 0 }.

Push for each a, skip b's (no stack change), pop one for each c:

δ(q0, a, Z0) = {(q0, aZ0)}    δ(q0, a, a) = {(q0, aa)}
δ(q0, ε, Z0) = {(q1, Z0)}     δ(q0, ε, a) = {(q1, a)}       end of a's
δ(q1, b, Z0) = {(q1, Z0)}     δ(q1, b, a) = {(q1, a)}       skip b's
δ(q1, ε, Z0) = {(q2, Z0)}     δ(q1, ε, a) = {(q2, a)}       end of b's
δ(q2, c, a)  = {(q2, ε)}
δ(q2, ε, Z0) = {(q3, Z0)}     F = {q3}

The ε-moves make this version nondeterministic, which is the easiest way to write it. The language is in fact a DCFL; a deterministic version moves from q0 on reading the first b or c instead of using ε-moves.

Q4. True or false: a DPDA accepting by empty stack can accept { a, aa }.

False. a is a proper prefix of aa. After accepting a, the stack is empty, so the DPDA cannot make any further move to read the second a. (With final-state acceptance, a DPDA accepts it easily.)

Q5. Interview: why is a single stack enough for anbn but not for anbncn?

For anbn, the a's are pushed and the b's consume them. For anbncn, checking n b's against n a's pops the a's, so the information about n is gone when the c's arrive. Pushing the b's instead loses the comparison with the a's. A proof that no PDA can work uses the pumping lemma in Pumping Lemma for Context-Free Languages.


Summary

  • PDA = finite automaton + one stack. 7-tuple (Q, Σ, Γ, δ, q0, Z0, F).

  • Each move: read a symbol or ε, pop the top X, push a string γ (leftmost symbol on top), change state.

  • IDs (q, w, γ) and ⊢ give a precise trace.

  • Acceptance by final state or by empty stack; equivalent for NPDAs.

  • Design: push what must be matched later, pop when matching, use Z0 to detect zero, use nondeterminism to guess (the middle, or which condition holds).

  • DPDAs are weaker than NPDAs: Regular ⊂ DCFL ⊂ CFL; wwR is the standard CFL that is not a DCFL.

A stack remembers an unbounded amount, but only in last-in, first-out order. That is exactly enough to match nested pairs, and exactly why it fails on three-way counting.