Pushdownautomat

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