Bezkontextové jazyky

Definice: Zásobníkový automat $A=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, kde

• $Q$ - množina stavů
• $\Sigma$ - vstupní abeceda
• $\Gamma$ - zásobníková abeceda
• $\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to \mathcal{P}(Q\times {\Gamma }^{\ast })$, kde přechod $\delta (q,a,X)\in (p,\gamma )$ znamená, že na zásobníku se $X$ nahradí za $\gamma$.
• $q_0$ - počáteční stav
• $Z_0$ - počáteční zásobníkový symbol
• $F$ - nepovinná množina přijímacích stavů Rozlišujeme dva typy přijímaných jazyků a sice $L(A)$ jako jazyk přijímaný koncovými stavy a $N(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