Push-Down Automaton (PDA)

Extends the concept of an Automaton with a stack, i.e., it can count. The automaton needs to go through every input character and every item on the stack before finishing.

Structure

PDA = (Q,\Sigma,\Gamma,\delta,q_0,F)

• Q: Non-empty set of states
• \Sigma: Input alphabet
• \Gamma: Stack alphabet
• \delta: P Q \times \Sigma_\epsilon \times \Gamma_\epsilon \to \mathcal{P}(Q \times \Sigma_\epsilon)
• q_0: Initial state
• F: Set of valid end states

Lemma: A language is context free if it can be recognized by a PDA. Lemma: A language can be recognized by a PDA if it is context free.

Notation

The PDA extends the DFA and NFA state transition notation with an additional \text{remove} \to \text{add}.

• Push: \epsilon \to a
• Pop: a \to \epsilon
• Swap: a \to b

A \$ often indicates the end of the stack, i.e., if you read this you have reached the last character. This is used in combination with an initial empty transition \epsilon,\epsilon\to\$ to initialize the stack.