Introduction
Pushdown automata (PDAs) are computational models that extend finite automata by adding a stack. This additional memory allows them to recognize context-free languages, which are more powerful than regular languages.
PDAs are fundamental to:
- Parsing programming languages
- Syntax analysis in compilers
- Natural language processing
- Formal language theory
In this article, we’ll explore pushdown automata and their relationship to context-free grammars.
Pushdown Automaton Basics
Definition
A pushdown automaton consists of:
- States (Q): Finite set of states
- Input Alphabet (Σ): Finite set of input symbols
- Stack Alphabet (Γ): Finite set of stack symbols
- Transition Function (δ): Rules for state and stack transitions
- Start State (q₀): Initial state
- Start Stack Symbol (Z₀): Initial stack symbol
- Accept States (F): Set of accepting states
Formal Definition:
M = (Q, Σ, Γ, δ, q₀, Z₀, F)
Transition Function
Notation:
δ(q, a, X) = {(q', α), ...}
q: current state
a: input symbol (or ε)
X: top stack symbol
q': next state
α: string to push on stack
Interpretation:
- Read input symbol a (or ε for no input)
- Pop stack symbol X
- Push string α onto stack
- Move to state q'
PDA Operation
Step-by-Step Execution
Algorithm:
1. Start in state q₀ with Z₀ on stack
2. For each input symbol:
a. Read symbol a
b. Pop top stack symbol X
c. Apply transition δ(q, a, X)
d. Push resulting string onto stack
e. Move to new state
3. Accept if:
- All input consumed AND
- In accept state (or stack empty)
Example: Recognizing {aⁿbⁿ}
PDA:
States: q0, q1, q2
Input Alphabet: {a, b}
Stack Alphabet: {A, Z}
Start State: q0
Start Stack Symbol: Z
Accept States: q2
Transitions:
δ(q0, a, Z) = {(q0, AZ)}
δ(q0, a, A) = {(q0, AA)}
δ(q0, b, A) = {(q1, ε)}
δ(q1, b, A) = {(q1, ε)}
δ(q1, ε, Z) = {(q2, Z)}
Execution for “aabb”:
State: q0, Input: aabb, Stack: Z
Read 'a', pop Z, push AZ
State: q0, Input: abb, Stack: AZ
Read 'a', pop A, push AA
State: q0, Input: bb, Stack: AAZ
Read 'b', pop A, push ε
State: q1, Input: b, Stack: AZ
Read 'b', pop A, push ε
State: q1, Input: ε, Stack: Z
Read ε, pop Z, push Z
State: q2, Input: ε, Stack: Z
Accept: YES
Deterministic vs Non-Deterministic PDAs
Deterministic PDA (DPDA)
A DPDA has at most one transition for each (state, input, stack) combination.
Characteristics:
- Unique next state and stack operation
- Efficient recognition
- Cannot recognize all context-free languages
Example:
δ(q, a, X) = {(q', α)} (at most one)
Non-Deterministic PDA (NPDA)
An NPDA can have multiple transitions for each (state, input, stack) combination.
Characteristics:
- Multiple possible paths
- Can recognize all context-free languages
- Requires exploring all paths
Example:
δ(q, a, X) = {(q₁, α₁), (q₂, α₂), ...}
Equivalence
Theorem: Every context-free language is recognized by some NPDA.
Proof Idea: Convert CFG to NPDA using grammar rules.
PDA Construction from CFG
Algorithm
Input: Context-free grammar G = (V, Σ, R, S)
Output: NPDA M = (Q, Σ, Γ, δ, q₀, Z₀, F)
Construction:
1. Q = {q₀, q₁}
2. Σ = terminals of G
3. Γ = V ∪ Σ ∪ {Z₀}
4. Z₀ = new symbol
5. F = {q₁}
Transitions:
δ(q₀, ε, Z₀) = {(q₁, SZ₀)}
For each production A → α:
δ(q₁, ε, A) = {(q₁, α)}
For each terminal a:
δ(q₁, a, a) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₁, ε)}
Example: Converting Grammar to PDA
Grammar:
S → aSb | ε
PDA:
States: q0, q1
Input Alphabet: {a, b}
Stack Alphabet: {S, a, b, Z}
Start State: q0
Start Stack Symbol: Z
Accept States: q1
Transitions:
δ(q0, ε, Z) = {(q1, SZ)}
δ(q1, ε, S) = {(q1, aSb), (q1, ε)}
δ(q1, a, a) = {(q1, ε)}
δ(q1, b, b) = {(q1, ε)}
δ(q1, ε, Z) = {(q1, ε)}
Acceptance Modes
Acceptance by Final State
Accept if:
- All input consumed
- In accept state
Example:
Accept states: {q2}
Accept if reach q2 after consuming all input
Acceptance by Empty Stack
Accept if:
- All input consumed
- Stack is empty
Example:
Accept if stack empty after consuming all input
Equivalence
Both acceptance modes are equivalent (can convert between them).
Complexity Analysis
Time Complexity
Recognition: O(n³) in worst case
- n: input length
- Requires exploring all possible paths (NPDA)
Space Complexity
Stack: O(n)
- Stack can grow to at most n symbols
Limitations of PDAs
What PDAs Cannot Recognize
Equal a’s, b’s, and c’s:
L = {aⁿbⁿcⁿ | n ≥ 0}
Cannot recognize (needs two stacks)
Palindromes with marker:
L = {wcw^R | w ∈ {a,b}*}
Can recognize (with marker)
Palindromes without marker:
L = {ww^R | w ∈ {a,b}*}
Cannot recognize (needs lookahead)
Glossary
- Pushdown automaton: Finite automaton with stack
- Stack: Last-in-first-out memory
- Stack symbol: Symbol stored on stack
- Transition: State and stack change
- DPDA: Deterministic pushdown automaton
- NPDA: Non-deterministic pushdown automaton
- Acceptance by final state: Accept in accept state
- Acceptance by empty stack: Accept with empty stack
- Context-free language: Language recognized by PDA
Practice Problems
Problem 1: PDA Design
Design a PDA for {aⁿbⁿ | n ≥ 0}.
Solution:
States: q0, q1, q2
Input Alphabet: {a, b}
Stack Alphabet: {A, Z}
Start State: q0
Start Stack Symbol: Z
Accept States: q2
Transitions:
δ(q0, a, Z) = {(q0, AZ)}
δ(q0, a, A) = {(q0, AA)}
δ(q0, b, A) = {(q1, ε)}
δ(q1, b, A) = {(q1, ε)}
δ(q1, ε, Z) = {(q2, Z)}
Problem 2: PDA Execution
Trace execution of PDA from Problem 1 on input “aabb”.
Solution:
(q0, aabb, Z) ⊢ (q0, abb, AZ) ⊢ (q0, bb, AAZ) ⊢
(q1, b, AZ) ⊢ (q1, ε, Z) ⊢ (q2, ε, Z)
Accept: YES
Problem 3: Grammar to PDA
Convert grammar S → aSb | ε to PDA.
Solution:
States: q0, q1
Input Alphabet: {a, b}
Stack Alphabet: {S, a, b, Z}
Start State: q0
Start Stack Symbol: Z
Accept States: q1
Transitions:
δ(q0, ε, Z) = {(q1, SZ)}
δ(q1, ε, S) = {(q1, aSb), (q1, ε)}
δ(q1, a, a) = {(q1, ε)}
δ(q1, b, b) = {(q1, ε)}
δ(q1, ε, Z) = {(q1, ε)}
Problem 4: Language Recognition
Can a PDA recognize {aⁿbⁿcⁿ | n ≥ 0}? Why or why not?
Solution:
No. A PDA has only one stack, so it can match two sequences
(a's with b's, or b's with c's) but not three independently.
Would need two stacks (linear bounded automaton).
Related Resources
Online Platforms
- Khan Academy Computer Science
- Coursera Automata Theory
- MIT OpenCourseWare
- Brilliant.org Computer Science
- Stanford CS103
Interactive Tools
- JFLAP - PDA simulator
- Automata Visualizer - Visualize PDAs
- PDA Simulator - Simulate PDAs
- Grammar to PDA Converter - Convert grammars
- Automata Tester - Test automata
Recommended Books
- “Introduction to Automata Theory, Languages, and Computation” by Hopcroft, Motwani, Ullman
- “Theory of Computation” by Sipser
- “Elements of the Theory of Computation” by Lewis & Papadimitriou
- “Formal Languages and Their Relation to Automata” by Hopcroft & Ullman
- “Computability and Complexity” by Papadimitriou
Academic Journals
- Journal of Computer and System Sciences
- Theoretical Computer Science
- ACM Transactions on Computational Logic
- Information and Computation
- Formal Aspects of Computing
Software Tools
- JFLAP - Automata simulator
- Graphviz - Graph visualization
- Automata Toolkit - Automata tools
- Language Tools - Language tools
- Regex Tester - Regular expression tester
Conclusion
Pushdown automata extend finite automata with stack memory:
- PDAs recognize context-free languages
- Stack provides additional memory
- Equivalence with context-free grammars
- Deterministic vs non-deterministic variants
- Practical applications in parsing and compilation
Understanding PDAs is essential for compiler design and formal language theory.
In the next article, we’ll explore Turing machines, the most powerful computational model.
Next Article: Turing Machines: Computation Model
Previous Article: Deterministic vs Non-Deterministic Automata
Comments