Uogólniony automat ze stosem (ang. Generalized Pushdown Automaton, GPDA) Uogólniony automat ze stosem jest rozszerzeniem automatu ze stosem o możliwość zapisu i usuwania ciągów ze stosu w jednym kroku.
Formalnie, uogólniony automat ze stosem jest definiowany jako szóstka gdzie i są zdefiniowane tak samo jak dla automatów ze stosem.
jest funkcją przejścia.
Reguły obliczeń dla GPDA są takie same jak dla PDA, z wyjątkiem tego że i są ciągami, a nie symbolami.
GPDA i PDA są równoważne: dla każdego języka rozpoznawanego przez GPDA istnieje PDA rozpoznający ten język, i odwrotnie.
Dowód równoważności powyższych klas automatów można przeprowadzić, używając następującej symulacji:
Niech będzie przejściem GPDA
gdzie
Skonstruujmy następujące przejścia dla PDA:
Kategoria:Teoria automatów