Pushdownautomat
Utseende
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
[rediger | rediger kilde]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
[rediger | rediger kilde]- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Seksjon 2.2: Pushdown Automata, ss. 101–114.