Zásobníkový automat (PDA) Zásobníkový automat (PDA) je $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$, kde
\begin{description}
\item[$Q$] konečná množina stavů
\item[$\Sigma$] neprázdná konečná množina vstupních symbolů
\item[$\Gamma$] neprázdná konečná zásobníková abeceda
\item[$\delta$] přechodová funkce $\delta: Q\times (\Sigma\cup \{\lambda\})\times \Gamma \rightarrow P(_{FIN}(Q \times X^*)$, $(q,a,X)=(p,\gamma)$
\begin{itemize}
\item[] kde $p$ je nový stav a $\gamma$ je řetězec zásobníkových symbolů, který nahradí $X$ na vrcholu zásobníku
\end{itemize}
\item[$q_0\in Q$] počáteční stav
\item[$Z_0\in \Gamma$] Počáteční zásobníkový symbol. Víc na začátku na zásobníku není.
\item[$F$] Množina přijímajících (koncových) stavů
\end{description} |