4.1The PDA and how it accepts
The idea
A pushdown automaton is a finite automaton with a stack. Each move looks at the input symbol and the stack top, then pushes or pops.
Think of it like this: A stack of plates: you can only touch the top plate, but you can stack as many as you like.
Why it exists
The stack gives unbounded counting, enough for nested structures like aⁿbⁿ and balanced brackets.
How it works
- Read input (or ε) and look at the top of the stack.
- Move to a new state and replace the top by a string.
- Accept by final state (end of input in a final state) or by empty stack.
- For nondeterministic PDAs both modes are equally powerful.
Worked example: aⁿbⁿ
Push A for each a; on the first b start popping; accept when the stack is back to Z at the end of the input.
Now play with it
- →Step through
aaabbband watch the stack grow then shrink. - →Change the input to
aaband see the rejection.
Moves (state, input, pop → state, push):
input: aaabbb
- Start in q0 with stack Z
- δ(q0, a, Z) → (q0, AZ)
- δ(q0, a, A) → (q0, AA)
- δ(q0, a, A) → (q0, AA)
- δ(q0, b, A) → (q1, ε)
- δ(q1, b, A) → (q1, ε)
- δ(q1, b, A) → (q1, ε)
- δ(q1, ε, Z) → (q2, 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
A PDA with no stack is
Exam notes (the dense version)
A PDA is an NFA plus a stack: δ(q, input or ε, stack top) gives (new state, string to push). It accepts by final state or by empty stack; for nondeterministic PDAs the two modes are equivalent in power.
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.