PDA Transition Functions
You'll learn: How a pushdown automaton decides what to do at each step by reading input, manipulating its stack, and changing states.
What Is a Transition Function?
A PDA's transition function defines all legal moves the machine can make. Unlike a DFA that only reads input and changes state, a PDA's transition function must handle three things simultaneously: the current state, the input symbol being read, and the top symbol on the stack.
The Three-Part Decision
Think of a PDA transition like a vending machine that checks your coin, looks at what product is currently "on top" internally, and then decides what to dispense and how to update its inventory.
Each transition specifies:
- Input symbol to read (or ε to read nothing)
- Stack symbol to pop from the top (or ε if no pop needed)
- Action to take: move to a new state and push zero or more symbols onto the stack
Transition Notation
A transition is often written as:
δ(q, a, X) → (p, γ)
Where:
q= current statea= input symbol (or ε)X= top stack symbol (or ε)p= next stateγ= string of symbols to push (could be empty, one symbol, or multiple)
How It Works
When the PDA is in state q, sees input a, and has X on top of the stack, it can:
- Consume
afrom the input (unlessais ε) - Pop
Xfrom the stack (unlessXis ε) - Push
γonto the stack (right-to-left, so the leftmost symbol ends up on top) - Move to state
p
Key Takeaway: A PDA transition function coordinates three actions—reading input, popping the stack top, and pushing new symbols—to enable stack-based computation that recognizes context-free languages.