プッシュダウン・オートマトン
r m } {\displaystyle q_{j}\notin \{r_{0},r_{1},\dots r_{m}\}} であるとき、 ( q j + 1 , b j + 1 ) ∈ δ ( q j , ε , a j + 1 ) {\displaystyle (q_{j+1},b_{j+1})\in \delta (q_{j},\epsilon ,a_{j+1})} ここで a j + 1 {\displaystyle a_{j+1}} と b j + 1 {\displaystyle b_{j+1}} は計算定義 1 で定義されたもの。
r m = q n {\displaystyle r_{m}=q_{n}} かつ r m ∈ F {\displaystyle r_{m}\in F}
これら定義はスタックが空かどうかの判定機構を提供していない点に注意。スタックが空かどうかを判定するには、計算前にスタックに特殊記号を書いておき、PDA がスタックを読んでその記号が読み取れた場合は空であると判断する。形式的には、 δ ( q 0 , ε , ε ) = { ( q 1 , $ ) } {\displaystyle \delta (q_{0},\epsilon ,\,\epsilon )=\{(q_{1},\$)\}} という遷移を導入する。ここで、$ はその特殊記号である。
どう操作するかは状態遷移表によって決定される。
まとめると、入力信号と現在状態とスタック上の文字によって状態遷移すると共に、必要に応じてスタック操作を行う。
有限オートマトンでも特に非決定性有限オートマトンに基づいている場合、「非決定性プッシュダウン・オートマトン」(NPDA、nondeterministic pushdown automaton)と呼ばれる。決定性有限オートマトンに基づいている場合、「決定性プッシュダウン・オートマトン(英語版)」(DPDA、deterministic pushdown automaton)と呼ばれる。非決定性とは、入力信号と状態とスタック上の文字を与えられても次の遷移先が一意に決定されない場合があることを意味する。
有限オートマトンにふたつのスタックを接続することもでき、これは事実上チューリングマシンと等価な非常に強力なデバイスとなる。線形拘束オートマトンはプッシュダウン・オートマトンよりも強力だが、チューリングマシンよりは非力である。