Definition:Pushdown Automaton

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Definition

A pushdown automaton is a septuple:

$M = \struct {Q, \Sigma, \Gamma, \delta, q_0, Z, F}$

where:

$Q$ is a finite set of states

the input alphabet $\Sigma$ is a finite set

the stack alphabet $\Gamma$ is a finite set

the transition relation $\delta$ is a finite subset of $Q \times \paren {\Sigma \cup \set {\varepsilon} } \times \Gamma \times Q \times \Gamma^*$

$q_0 \in Q$ is the start state

$Z \in \Gamma$ is the initial stack symbol

$F \subseteq Q$ is the set of accepting states.

An instantaneous description is any triple of state, input and stack:

$\struct {p, w, \beta} \in Q \times \Sigma^* \times \Gamma^*$

A computation step is:

$\struct {p, a x, A \gamma} \map {\vdash_M} {q, x, \alpha \gamma} \iff \struct {p, a, A, q, \alpha} \in \delta$

$M$'s accepted language is:

$\map L M := \set {w \in \Sigma^* \mid \exists f \in F: \exists \gamma \in \Gamma^*: \struct {q_0, w, Z} \map { {\vdash_m}^*} {f, \varepsilon, \gamma} }$