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 \mathcal{P}(Q\times {\Gamma }_{\epsilon })$.
5. $q_0\in Q$ is the start state.
6. $F\subseteq Q$ is the set of accept states.

Computation

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

Language Class

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