Definition:Pushdown Automaton
Jump to navigation
Jump to search
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} }$