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.
Kategori:Formelle språk