Definice: Zásobníkový automat , kde
- - množina stavů
- - vstupní abeceda
- - zásobníková abeceda
- , kde přechod znamená, že na zásobníku se nahradí za .
- - počáteční stav
- - počáteční zásobníkový symbol
- - nepovinná množina přijímacích stavů Rozlišujeme dva typy přijímaných jazyků a sice jako jazyk přijímaný koncovými stavy a jazyk přijímaný prázdným zásobníkem.
Bezkontextové gramatiky jsou ekvivalentní jazykům definovaných pomocí zásobníkových automatů. Konstrukčně můžeme každou takovou gramatiku na zásobníkový automat převést