pushdown automaton

Angol

pushdown automaton (tsz. pushdown automatons)

(informatika) A pushdown automaton (PDA), magyarul veremautomaták egy olyan formális számítógépmodell, amely a véges automata kiterjesztése egy verem adattároló használatával. Ez a modell képes kezelni a kontextusfüggetlen nyelveket, amelyek komplexebb szerkezeteket is reprezentálnak, mint a véges automata által felismerhetők.

Egy állapotgépet (finite automaton) egészít ki egy veremmel, amely segítségével bővíthető az elfogadható nyelvek osztálya.
Az automata a bemeneti szimbólumokat olvassa, közben módosítja a verem tartalmát.
A verem lehetővé teszi, hogy az automata emlékezzen korábbi jelekre, így képes például beágyazott szerkezetek (mint zárójelek) felismerésére.

A PDA egy 7-es típusú struktúra:

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

${\textstyle Q}$ : véges állapotok halmaza
${\textstyle \Sigma }$ : bemeneti ábécé
${\textstyle \Gamma }$ : verem ábécé
${\textstyle \delta }$ : állapotátmenet függvény (olvasott szimbólum, verem teteje alapján)
${\textstyle q_{0}}$ : kezdőállapot
${\textstyle Z_{0}}$ : verem kezdő szimbóluma
${\textstyle F}$ : elfogadó állapotok halmaza

Az automata egyszerre olvashat egy bemeneti szimbólumot vagy akár üres lépést ( ${\textstyle \epsilon }$ -átmenet).
Megvizsgálja a verem tetejét.
Állapotot vált, és módosítja a verem tartalmát (elemet tesz rá vagy vesz le).
Elfogad egy szót, ha a bemenet végére ér és elfogadó állapotba kerül, vagy ha a verem üres lesz (attól függően, milyen elfogadási módot alkalmaz).

A PDA-k a kontextusfüggetlen nyelvek felismerői.
Alapvető szerepük van a nyelvfeldolgozásban, például a programozási nyelvek szintaxisának elemzésében (parser-ek).
Az egyszerűbb nyelveknél (pl. reguláris nyelveknél) a véges automata elegendő, de a komplexebb szerkezetekhez (mint zárójelezett kifejezések) PDA szükséges.

Fogalom	Leírás
Pushdown automaton (PDA)	Véges automata egy veremmel, komplex nyelvek felismerésére
Képesség	Kontextusfüggetlen nyelvek felismerése
Alkalmazás	Szintaktikai elemzés, fordítók