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.  er mengda av strengene over alfabetet  og  er den tomme strengen.

  er ei endelig mengde av tilstander i automaten
  er ei endelig mengde som kalles inputalfabetet
  er ei endelig mengde som kalles stakkalfabetet
  er ei endelig delmengde av , overgangsrelasjonen.
  er starttilstanden
  er de initielle stakksymbolene
  er ei mengde bestående av de aksepterende tilstandene. Beskrevet som ei delmengde av alle tilstander for automaten.

Litteratur 
  Seksjon 2.2: Pushdown Automata, ss. 101–114.

Formelle språk