Pushdown Automata — Theory of Computation

⭐ Why Do We Need PDA?

Think of trying to check a math expression like:

((a + b) – (c + d))

A finite automaton cannot keep track of how many opening brackets ( are waiting for closing ones ).
But a PDA can push each ( onto the stack, and pop it when ) appears.

So PDAs are perfect for things like:

• Balanced parentheses
• Palindromes
• Languages where “something must match something else later”

---

⭐ How Does a PDA Work?

A PDA makes decisions based on three things at a time:

1. Current state
2. Current input symbol
3. Top of the stack

From these, it decides operations:

• Push something to the stack
• Pop something from the stack
• Change the state
• Do all, some, or none of them

---

⭐ Formal Definition (Explained Simply)

A PDA is a 7-tuple:

(Q, Σ, Γ, δ, q0, Z0, F)

But let’s explain this in human language:

• Q → set of states
• Σ → input symbols
• Γ → stack symbols
• δ → transition rules
• q0 → starting state
• Z0 → initial symbol in stack
• F → final/accepting states

Think of it as a robot with instructions, pockets of memory, and a starting point.

---

🎯 Example 1: PDA for Balanced Parentheses

Let’s create a PDA that checks strings like:

(), (()), (()()), (()(()))

These strings belong to language:

L = { balanced parentheses }

✔ Logic behind it:

• When we see (, push it onto the stack.
• When we see ), pop a ( from the stack.
• If the stack is empty at the end → string is balanced.

---

📘 Simple Diagram (Conceptual)

          push '('
   ---> (q0) ---------------->
      ^                       |
      |                       |
      <-----------------------
          pop '('

This is just a conceptual sketch.
It means: stay in the same state, pushing or popping as needed.

---

✔ Transition Table (Simple Form)

Input	Stack Top	Action
(	anything	push (
)	(	pop
empty	Z0	accept

---

⭐ Example 2: PDA for aⁿbⁿ (same number of a’s and b’s)

This language includes strings like:

ab, aabb, aaabbb, …

The rule:
Number of a’s must equal number of b’s.

✔ PDA Strategy:

• For every a, push an A.
• For every b, pop an A.
• If stack empties exactly when input ends → accept.

---

📘 Diagram (Easy to Visualize)

            read 'a', push A
   ---> (q0) -----------------------> (q1)
             read 'b', pop A
                  ^         |
                  |_________|

Meaning:

• First state (q0) handles all the a’s.
• When b’s begin, we move to q1 and start popping.

---

⭐ Small, Friendly Example

Let’s test the string:

aaabbb

Step-by-step:

1. Read a → push A
2. Read a → push A
3. Read a → push A
4. Read b → pop A
5. Read b → pop A
6. Read b → pop A
7. Stack is empty → ACCEPT

We can clearly see how the stack helps with counting.

---

⭐ Why PDAs Matter (In Real Life)

PDAs form the backbone of:

• Compilers
• Parsing algorithms
• Checking valid code structures
• Understanding nested patterns in programming languages

Whenever you run a program and the compiler checks whether your parentheses or loops are written correctly, somewhere inside, a PDA-like logic is working.