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. $\Gamma ^{*}$ er mengda av strengene over alfabetet $\Gamma$ og $\varepsilon$ er den tomme strengen.

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$

• $\,Q$ er ei endelig mengde av tilstandar i automaten
• $\,\Sigma$ er ei endelig mengde som vert kalla inputalfabetet
• $\,\Gamma$ er ei endelig mengde som vert kalla stakkalfabetet
• $\,\delta$ er ei endelig delmengde av $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$, overgangsrelasjonen.
• $\,q_{0}\in \,Q$ er starttilstanden
• $\ Z\in \,\Gamma$ er dei initielle stakksymbola
• $F\subseteq Q$ 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.