プッシュダウンオートマトン
等価
定義
$ P = \lang Q,\Sigma,\Gamma,\delta,q_0,F \rang
$ Q: 有限の状態の集合
$ \Sigma: 有限の入力記号の集合
$ \Gamma:有限のスタックアルファベットの集合
$ \delta: $ Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \mapsto 2^{(Q \times \Gamma_\varepsilon )}，状態遷移関数
ただし
$ \Sigma_\varepsilon = \Sigma \cup \{\varepsilon\}
$ \Gamma_\varepsilon = \Gamma \cup \{\varepsilon\}
$ q_0 \in Q: 初期状態
$ F \sube Q: 受理状態の集合