Redigerer Pushdownautomat

En '''pushdownautomat''' er en type automat med en [[Stakk (datastruktur)|stakk]]. Det kan tenkes på som en forlengelse av ei [[Endelig tilstandsmaskin|tilstandsmaskin]] ved at man for hver overgang mellom tilstandene har muligheten til å manipulere en stakk. En deterministisk pushdownautomat kan gjenkjenne alle deterministisk [[Kontekstfritt språk|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. <math>\Gamma^{*}</math> er mengda av strengene over alfabetet <math>\Gamma</math> og <math>\varepsilon</math> er den tomme strengen.

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

== Litteratur ==
* {{cite book|author=[[Michael Sipser]]|year=1997|title=Introduction to the Theory of Computation|url=https://archive.org/details/introductiontoth00sips|publisher=PWS Publishing|isbn=0-534-94728-X}} Seksjon 2.2: Pushdown Automata, ss.&nbsp;101&#x2013;114.

[[Kategori:Formelle språk]]