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

Introduction to Pushdown Automata

Definition of PDA, components (states, stack, transitions), and how PDAs extend finite automata with stack memory.

Introduction to Pushdown Automata

What you'll learn: How pushdown automata extend finite automata with stack memory to recognize context-free languages.

What is a Pushdown Automaton?

A Pushdown Automaton (PDA) is a computational model that recognizes context-free languages—the languages generated by context-free grammars. Think of it as a finite automaton (like a DFA or NFA) that carries a stack as auxiliary memory.

While finite automata can only "remember" information through their current state, a PDA can push symbols onto a stack and pop them off later. This extra memory lets PDAs recognize patterns that require matching or counting, like balanced parentheses or nested structures.

Components of a PDA

A PDA consists of:

  1. States: A finite set of control states (like in DFAs/NFAs)
  2. Input alphabet: The symbols the PDA reads from input
  3. Stack alphabet: The symbols that can be pushed onto or popped from the stack
  4. Start state: Where computation begins
  5. Start stack symbol: An initial marker on the stack
  6. Accepting states: States that indicate acceptance (some PDAs accept by empty stack instead)

How PDAs Extend Finite Automata

The crucial difference: transitions depend on three things:

  • The current state
  • The current input symbol (or ε for epsilon transitions)
  • The top symbol on the stack

A transition can:

  • Move to a new state
  • Push a symbol onto the stack
  • Pop the top symbol from the stack

This stack memory allows PDAs to "remember" unbounded information—perfect for matching nested structures that context-free grammars describe.

Key Takeaway: Pushdown Automata are finite automata augmented with a stack, enabling them to recognize context-free languages by storing and retrieving information during computation.