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:
- Start with an empty stack
- When you see '(': Push it onto the stack (recording that we need a matching close)
- When you see ')': Pop from the stack (matching it with the most recent open)
- 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.