Pushdown Automata (PDA), DPDA vs NPDA & Acceptance Modes

A Pushdown Automaton (PDA) augments a finite state automaton with an unbounded Last-In-First-Out (LIFO) stack memory.

Formally defined as a 7-tuple: M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F), where:

- \Gamma: Finite stack alphabet.

- Z_0 \in \Gamma: Initial start symbol on the stack.

- \delta: Transition function mapping Q × (\Sigma \cup {\epsilon}) × \Gamma \to 2^{Q × \Gamma^*}.

Two Acceptance Modes:

1. Acceptance by Final State (L(M)): The input is fully consumed and the PDA halts in an accepting state q \in F (stack contents are ignored).

2. Acceptance by Empty Stack (N(M)): The input is fully consumed and the stack becomes completely empty (state is ignored).

Equivalence Theorem: For Non-deterministic PDAs (NPDA), L(M) and N(M) accept the EXACT SAME class of languages (Context-Free Languages).

In finite automata, determinism and non-determinism have identical expressive power (DFA = NFA).

For Pushdown Automata, determinism is strictly weaker:

$DCFL \subsetneq CFL$

- Deterministic Pushdown Automata (DPDA): At most one transition is possible for any state, input symbol (or \epsilon), and top-of-stack symbol. The languages accepted by DPDA are Deterministic Context-Free Languages (DCFL).

- Classic Distinctions:

- Even-length palindromes L = { w w^R \mid w \in \Sigma^* } is CFL but NOT DCFL (requires non-determinism to guess the midpoint).

- Marked palindromes L = { w c w^R \mid w \in \Sigma^* } IS DCFL (the center marker c signals when to switch from pushing to popping).

- L = { a^n b^n \mid n ≥ 1 } \cup { a^n b^{2n} \mid n ≥ 1 } is CFL but NOT DCFL.