Course contentsShow
← Computer Science
Lesson 1830 of 2,87241. Context-Free LanguagesFree lesson

PDA Transition Functions

How PDA transitions work: reading input symbols, popping/pushing stack symbols, and changing states.

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:

  1. Input symbol to read (or ε to read nothing)
  2. Stack symbol to pop from the top (or ε if no pop needed)
  3. 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 state
  • a = 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 a from the input (unless a is ε)
  • Pop X from the stack (unless X is ε)
  • 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.