← 🥞 Pushdown Automata
Subtopic 4 of 4

4.4Designing PDAs and counting

The idea

To design a PDA, push a marker for each symbol you will need to match later and pop one for each matching symbol.

Think of it like this: Keeping a tally by dropping a stone for each sheep out and removing one for each sheep in.

Why it exists

Designing and tracing PDAs is the standard exam skill.

How it works

  1. aⁿbⁿ: push per a, pop per b.
  2. aⁿb²ⁿ: push two per a (or pop one per two b's).
  3. Equal numbers of a and b in any order: push the symbol if the top is the same or empty, pop if different.
  4. One stack can compare only two counts, so aⁿbⁿcⁿ is impossible.

Worked example: Balanced parentheses

Push X on "(", pop on ")". (()()) ends with an empty stack: accepted; (() leaves X on the stack: rejected.

Now play with it

  • →Run the parenthesis PDA on (()()) and then (().
  • →Try the "equal a and b" PDA on abba.

Moves (state, input, pop → state, push):

δ(q0, (, Z) → (q0, XZ)δ(q0, (, X) → (q0, XX)δ(q0, ), X) → (q0, ε)δ(q0, ε, Z) → (q1, Z)
Z
state q0
input: (()())
  • Start in q0 with stack Z
  • δ(q0, (, Z) → (q0, XZ)
  • δ(q0, (, X) → (q0, XX)
  • δ(q0, ), X) → (q0, ε)
  • δ(q0, (, X) → (q0, XX)
  • δ(q0, ), X) → (q0, ε)
  • δ(q0, ), X) → (q0, ε)
  • δ(q0, ε, Z) → (q1, Z)
  • ACCEPT: all input read and the PDA is in a final state

Top of stack is at the top of the box. This one is deterministic.

Check yourself

Which cannot be accepted by any PDA?

Remember: One stack = one comparison.
Exam notes (the dense version)

Push a marker per symbol of the first block and pop one per symbol of the second (aⁿbⁿ). For aⁿb²ⁿ push two per a. One stack can compare one pair of counts, which is why aⁿbⁿcⁿ is out of reach. A PDA with two stacks is as powerful as a Turing machine.

Previous year questions: Pushdown Automata (2)

PYQs are grouped by topic, so this is the full set for Pushdown Automata; try the ones that match this subtopic. Open all 2 on the topic page.