📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT 4: PUSH DOWN AUTOMATA (PDA) (university of allahabad)

 

🔴 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:

M = (Q, Σ, Γ, δ, q₀, Z₀, F)

Where:

• Q → Finite set of states

• Σ → Input alphabet

• Γ → Stack alphabet

• δ → Transition function

• q₀ → Initial state

• Z₀ → Initial stack symbol

• F → Final states

---

✅ Transition Function

$$\delta : Q × (Σ ∪ \{ε\}) × Γ → P(Q × Γ^*)$$

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:

$$(q, w, γ)$$

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

• Only one transition is possible

---

✅ Key Points

• DPDA ⊂ PDA

• 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

• Uses stack to store variables

---

🔹 PDA → CFG

For every PDA, a CFG can be constructed that:

• Generates same language

• Uses transitions to define productions

---

🔁 Relationship Diagram

CFG  ⇄  PDA

---

6️⃣ PDA for Language aⁿbⁿ

Language:

L = { aⁿbⁿ | n ≥ 1 }

---

Working:

1. Push a onto stack for each input a

2. Pop one a for each b

3. 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

---

8️⃣ Applications of PDA

• Syntax checking

• Compiler design

• Expression evaluation

• Parsing in programming languages