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

PDAs for Balanced Parentheses

Building a PDA that recognizes strings of properly nested parentheses using stack operations.

PDAs for Balanced Parentheses

What you'll learn: How to build a pushdown automaton that recognizes strings of properly nested parentheses by leveraging stack operations.

The Core Idea

Balanced parentheses are a classic example of a context-free language that's not regular. Think of every opening parenthesis as creating a "debt" that must be paid with a closing parenthesis, and the stack is your ledger.

The PDA works like this:

  1. Start with an empty stack
  2. When you see '(': Push it onto the stack (recording that we need a matching close)
  3. When you see ')': Pop from the stack (matching it with the most recent open)
  4. Accept if: You've read the entire string AND the stack is empty

Why This Works

The stack naturally enforces the "last opened, first closed" property of balanced parentheses. It's like stacking plates: the last plate you put on top is the first one you must remove.

For example, with the string ((())):

  • Read (: stack becomes [(
  • Read (: stack becomes [(, (
  • Read (: stack becomes [(, (, (
  • Read ): pop, stack becomes [(, (
  • Read ): pop, stack becomes [(
  • Read ): pop, stack becomes [] (empty—accept!)

A string like ()) fails because when you try to pop for the third symbol, the stack is already empty—revealing the imbalance.

The Formal Transition

The PDA has transitions like:

  • (state q, input '(', stack top anything) → push '(' and stay in q
  • (state q, input ')', stack top '(') → pop '(' and stay in q
  • Accept by empty stack when input exhausted

Key Takeaway: PDAs recognize balanced parentheses by using the stack to match each closing parenthesis with its corresponding opening one, demonstrating why context-free languages are more powerful than regular languages.