Push Down Automata - Formal Definition

 

Context-Free Languages and Pushdown Automata

Why PDAs?

• CFGs describe context-free languages (CFLs) (e.g., programming languages via BNF).

• We want an automaton model for CFLs.

• Finite Automata (FA) are too weak:

  • FA have finite memory only.

  • Cannot handle unbounded counting.

---

Example: $L = \{a^n b^n \mid n \ge 0\}$

• Must count number of $a$’s to match with $b$’s.

• $n$ is unbounded → impossible with finite memory.

---

Example: $L = \{ww^R \mid w \in \Sigma^*\}$

• Need to store a sequence of symbols.

• Later, match them in reverse order.

• Requires more than just counting.

---

Solution: Use a Stack

• Stack = unlimited memory but restricted access:

  • Push → add symbol on top.

  • Pop → remove top symbol.

• Provides exactly the extra power needed.

---

Pushdown Automata (PDA)

• A PDA = Finite Automaton + Stack.

• Can recognize all context-free languages.

• Key idea: use the stack for counting and matching.

Control unit = finite states (like FA).
Stack = unbounded memory, last-in-first-out.

Pushdown Automaton (PDA) – Formal Definition

A Pushdown Automaton (PDA) is a 7-tuple

$$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$$

where:

1. Q – a finite set of states.

2. Σ – the input alphabet (finite set of symbols that the PDA can read from the input tape).

3. Γ – the stack alphabet (finite set of symbols that can be pushed to or popped from the stack).

4. δ – the transition function, defined as:

   $$\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \;\; \to \;\; \mathcal{P}(Q \times \Gamma^*)$$
   

   This means: given the current state, the current input symbol (or ε for empty move), and the top of the stack symbol, the PDA can move to a new state and replace the top of the stack with a string of stack symbols.

   (The use of $\mathcal{P}(\cdot)$ indicates nondeterminism: the machine may have multiple possible moves.)

5. q₀ ∈ Q – the start state.

6. Z₀ ∈ Γ – the initial stack symbol (marks the bottom of the stack).

7. F ⊆ Q – the set of accepting states.

Explanations 

• A PDA is like a Finite Automaton with memory, where the memory is provided by a stack.

• At each step, the PDA looks at:

  1. The current state.

  2. The next input symbol (or ε if it decides to make an ε-move).

  3. The symbol on the top of the stack.

  Based on these, it decides:

  • Which state to move to.

  • How to modify the stack (pop, push, or replace).

• The stack allows the PDA to keep track of potentially unbounded information (like counting nested parentheses), which a finite automaton cannot do.

• Acceptance criteria:
  A string is accepted by a PDA if, after reading the entire input, one of the following holds:

1. Final state acceptance: The PDA ends in an accepting state, regardless of stack content.

2. Empty stack acceptance: The PDA empties its stack, regardless of the final state.

Simple Example 

Language:

$$L = \{ a^n b^n \mid n \geq 0 \}$$

This is the classic non-regular language accepted by a PDA.

Idea:

• Push every a onto the stack.

• For every b, pop one a from the stack.

• Accept if stack is empty at the end