Pushdownautomat

En pushdownautomat er en type automat med en stakk. Det kan tenkes på som en forlengelse av ei tilstandsmaskin ved at man for hver overgang mellom tilstandene har muligheten til å manipulere en stakk. En deterministisk pushdownautomat kan gjenkjenne alle deterministisk kontekstfrie språk, mens en ikke-deterministisk pushdownautomat kan gjenkjenne alle kontekstfrie språk.

Deterministiske pushdownautomater er ofte brukt i design av parsere. Generelt er kontekstfrie språk og pushdownautomater viktige innenfor kompilatorteknikk.

Formell beskrivelse

En PDA er formelt definert som et 7-tuppel.

Beskrivelsen er angitt etter hvordan formelle språk generelt beskrives. $\Gamma ^{*}$ er mengda av strengene over alfabetet $\Gamma$ og $\varepsilon$ er den tomme strengen.

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$

• $\,Q$ er ei endelig mengde av tilstander i automaten
• $\,\Sigma$ er ei endelig mengde som kalles inputalfabetet
• $\,\Gamma$ er ei endelig mengde som kalles stakkalfabetet
• $\,\delta$ er ei endelig delmengde av $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$, overgangsrelasjonen.
• $\,q_{0}\in \,Q$ er starttilstanden
• $\ Z\in \,\Gamma$ er de initielle stakksymbolene
• $F\subseteq Q$ er ei mengde bestående av de aksepterende tilstandene. Beskrevet som ei delmengde av alle tilstander for automaten.

Litteratur

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Seksjon 2.2: Pushdown Automata, ss. 101–114.