Ein pushdownautomat er ein type automat med ein stakk. Det kan tenkjast på som ei utviding av ei tilstandsmaskin ved at ein for kvar overgang mellom tilstandane har høvet til å manipulera ein stakk. Ein deterministisk pushdownautomat kan kjenna att alle deterministisk kontekstfrie språk, medan ein ikkje-deterministisk pushdownautomat kan kjenna att alle kontekstfrie språk.
Deterministiske pushdownautomatar er ofte brukt i design av parsarar. Generelt er kontekstfrie språk og pushdownautomatar viktige innanfor kompilatorteknikk.
Formell skildring Ein pushdownautomat (PDA) er formelt definert som eit 7-tuppel.
Skildringa av han er gjeven etter korleis formelle språk generelt vert skildra. er mengda av strengene over alfabetet og er den tomme strengen.
er ei endelig mengde av tilstandar i automaten er ei endelig mengde som vert kalla inputalfabetet er ei endelig mengde som vert kalla stakkalfabetet er ei endelig delmengde av , overgangsrelasjonen. er starttilstanden er dei initielle stakksymbola er ei mengde av alle dei aksepterande tilstandane. Ho er ei delmengde av alle tilstandane 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. Kategori:Formelle språk Kategori:Matematisk modellering Kategori:Informatikk