I. Definition

The PDA is an automaton equivalent to the CFG in language-defining power.

• Only the nondeterministic PDA defines all the CFL’s.
• But the deterministic version models parsers.

Intuition: an $\varepsilon$-NFA with the additional power that it can manipulate a stack

Its moves are determined by:

1. The current state
2. The current input symbol
3. The current symbol on top of its stack

1. Formalism

$$ ⁍ $$

where

• $Q$: A finite set of states, like the states of a finite automaton.
• $\Sigma$: A finite set of input symbols
• $\Gamma$: A finite stack alphabet.
  • The set of symbols we are allowed to push onto the stack
• $\delta$: The transition function
  • $δ(q_1, a, Z)$ is a set of zero or more actions of the form $(q_2, \alpha)$.
• $q_0$: The start state
• $Z_0$: The start symbol (Stack should not be empty if state not final)
• $F$: The set of accepting states / final states

II. Moves of the PDA

If $δ(q, a, Z)$ contains $(p, \alpha)$ among its actions, then one thing the PDA can do in state $q$, with $a$ at the front of the input, and $Z$ on top of the stack is: