pushdown automaton

pushdown automaton (tsz. pushdown automatons)

1. (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:

$${\displaystyle 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.

• pushdown automaton - Szótár.net (en-hu)
• pushdown automaton - Sztaki (en-hu)
• pushdown automaton - Merriam–Webster
• pushdown automaton - Cambridge
• pushdown automaton - WordNet
• pushdown automaton - Яндекс (en-ru)
• pushdown automaton - Google (en-hu)
• pushdown automaton - Wikidata
• pushdown automaton - Wikipédia (angol)