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

PDA Configurations and Instantaneous Descriptions

Formal notation for PDA states: current state, remaining input, and stack contents at any moment.

PDA Configurations and Instantaneous Descriptions

You'll learn: How to formally capture the exact state of a pushdown automaton at any moment during computation.

What Is a Configuration?

A pushdown automaton processes input one symbol at a time, transitioning between states and manipulating its stack. At any given moment, we need to know three things:

  1. Current state – which control state the PDA is in
  2. Remaining input – what part of the input string hasn't been read yet
  3. Stack contents – what symbols are currently on the stack

Together, these three pieces of information form a configuration or instantaneous description (ID).

Formal Notation

A configuration is written as a triple:

(q, w, γ)

Where:

  • q is the current state
  • w is the remaining input string (what's left to process)
  • γ (gamma) is the stack contents, with the top of the stack written on the left

Example: If the PDA is in state q₂, has abb left to read, and the stack contains XZ (with X on top), we write:

(q₂, abb, XZ)

Why This Matters

Configurations let us describe PDA computation as a sequence of snapshots. We start with an initial configuration (q₀, input_string, Z₀) where Z₀ is the initial stack symbol. Each transition moves us to a new configuration, and we accept if we reach a configuration with empty remaining input (and possibly empty stack or an accepting state, depending on acceptance mode).

Key Takeaway: A PDA configuration (q, w, γ) is a complete snapshot of the automaton's state at one moment: which state it's in, what input remains, and what's on the stack.