Pushdown Automaton

Definition

A pushdown automaton is a 6-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ where:

1. $Q$ is a finite set of states.
2. $\Sigma$ is a finite input alphabet.
3. $\Gamma$ is the finite stack alphabet.
4. $\delta :Q\times {\Sigma }_{\epsilon }\times {\Gamma }_{\epsilon }\to Q\times {\Gamma }_{\epsilon }$, the transition function.
5. $q_0\in Q$ is the start state.
6. $F\subseteq Q$ is the set of accepting (or finishing) states.

Computation

The machine utilizes a logical stack for memory. Transitions depend on the current state, input symbol, and the symbol popped from the top of the stack.

Configuration

The configuration of a pushdown automaton at each timestep is a 3-tuple $(q,\gamma ,w)$:

1. The control state $q\in Q$.
2. The stack $\gamma :\mathrm{Stack}\Gamma$.
3. The remaining word $w:{\Sigma }^{\ast }$.

Initial configuration

Given an input word $w$, start with configuration $(q_0,[\perp ],w)$

Transitions

Let $q,w$ be the current state.

1. If $w$ is empty, then reject, else pop $x$ off $w$.
2. let

Language Class

Nondeterministic PDAs accept Context-Free Languages. Deterministic PDAs accept a strict subset known as deterministic context-free languages.