🔴 UNIT 4: PUSH DOWN AUTOMATA (PDA)
This unit is very important because it connects CFG and Automata, and questions often come for 5–10 marks.
1️⃣ Pushdown Automata (PDA)
✅ Definition
A Pushdown Automaton (PDA) is a computational model that:
-
Has finite control
-
Uses a stack (LIFO)
-
Recognizes Context-Free Languages (CFLs)
✅ Formal Definition
A PDA is a 7-tuple:
Where:
-
Q → Finite set of states
-
Σ → Input alphabet
-
Γ → Stack alphabet
-
δ → Transition function
-
q₀ → Initial state
-
Z₀ → Initial stack symbol
-
F → Final states
✅ Transition Function
Meaning:
-
Read input symbol or ε
-
Pop top of stack
-
Push new symbol(s)
2️⃣ Instantaneous Description (ID)
✅ Definition
An Instantaneous Description (ID) describes the current status of a PDA at any moment.
Format:
Where:
-
q → Current state
-
w → Remaining input
-
γ → Stack content
✅ Example
(q₀, 1011, Z₀)
Means:
-
Current state = q₀
-
Input remaining = 1011
-
Stack contains = Z₀
3️⃣ Acceptance by PDA
A PDA can accept a language in two ways:
🔹 1. Acceptance by Final State
A string is accepted if:
-
Input is completely read
-
PDA reaches a final state
✔ Stack content does not matter
🔹 2. Acceptance by Empty Stack
A string is accepted if:
-
Input is fully consumed
-
Stack becomes empty
✔ Final state not necessary
⚠ Important Theorem
👉 Both methods are equivalent in power
4️⃣ Deterministic Pushdown Automata (DPDA)
✅ Definition
A PDA is deterministic if:
-
For a given state, input symbol, and stack symbol
✅ Key Points
-
DPDA recognizes deterministic CFL
-
Not all CFLs are accepted by DPDA
✅ Example
Language:
L = { aⁿbⁿ | n ≥ 1 }
✔ Can be accepted by DPDA
❌ Example
L = { wwʳ | w ∈ {a,b}* }
✖ Cannot be accepted by DPDA
5️⃣ Relationship Between PDA and CFG
🔹 Important Theorem
A language is context-free if and only if it is accepted by a PDA
🔹 CFG → PDA
For every CFG, there exists a PDA that:
-
Simulates leftmost derivation
🔹 PDA → CFG
For every PDA, a CFG can be constructed that:
-
Generates same language
-
Uses transitions to define productions
🔁 Relationship Diagram
6️⃣ PDA for Language aⁿbⁿ
Language:
L = { aⁿbⁿ | n ≥ 1 }
Working:
-
Push
aonto stack for each inputa -
Pop one
afor eachb -
Accept when stack is empty
Stack Behavior:
| Input | Stack |
|---|---|
| a | push a |
| a | push a |
| b | pop a |
| b | pop a |
7️⃣ Difference: FA vs PDA
| Finite Automata | Pushdown Automata |
|---|---|
| No stack | Has stack |
| Recognizes regular languages | Recognizes CFL |
| Limited memory | Infinite memory (stack) |
| DFA/NFA | PDA |
