プッシュダウン・オートマトン（"Pushdown Automaton"）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。スタック操作とはある特定の文字をスタックにプッシュすることやスタックのトップをポップすることを意味する。また、PDAはスタックを操作せずにそのままにしておくこともできる。どう操作するかは状態遷移表によって決定される。まとめると、入力信号と現在状態とスタック上の文字によって状態遷移すると共に、必要に応じてスタック操作を行う。有限オートマトンでも特に非決定性有限オートマトンに基づいている場合、「非決定性プッシュダウン・オートマトン」（NPDA）と呼ばれる。決定性有限オートマトンに基づいている場合、「」（DPDA）と呼ばれる。非決定性とは、入力信号と状態とスタック上の文字を与えられても次の遷移先が一意に決定されない場合があることを意味する。有限オートマトンにふたつのスタックを接続することもでき、これは事実上チューリングマシンと等価な非常に強力なデバイスとなる。線形拘束オートマトンはプッシュダウン・オートマトンよりも強力だが、チューリングマシンよりは非力である。形式的には、PDA は以下の6-タプルで定義される。formula_1ここで、任意のPDA、formula_1 について、計算経路の順序は (n+1)-タプル formula_12 で表され（ここで formula_13 0 ）、以下の条件が成り立つ。直観的に、PDA での計算の任意の時点で、スタックのトップから記号を読み取ってそれを他の記号に置換するか、置換せずに単にスタックのトップを削除するか、あるいは読み取らずにスタックに新たに記号を追加するか、なにもしないかという選択肢がある。これらは連立方程式 formula_19で制御される。formula_20 は、(i+1)番目の状態遷移の直前のスタックの内容であり、formula_21 はスタックのトップから除去される記号である。formula_22 は (i+1)番目の状態遷移の直後のスタックの内容であり、formula_23は (i+1)番目の状態遷移に伴ってスタックに追加される記号である。formula_21 も formula_23 も formula_26 の可能性もある。formula_35 の場合、計算経路はシングルトンとなるformula_36。任意の入力formula_37 について、formula_38 であり、M が w を受容するのは、計算経路 formula_39 と有限の状態列 formula_40が存在し、以下が成り立つ場合である。これら定義はスタックが空かどうかの判定機構を提供していない点に注意。スタックが空かどうかを判定するには、計算前にスタックに特殊記号を書いておき、PDA がスタックを読んでその記号が読み取れた場合は空であると判断する。形式的には、formula_56 という遷移を導入する。ここで、$ はその特殊記号である。言語 formula_57 を認識するPDAの形式定義は以下の通りである。formula_58formula_59formula_60formula_61formula_62formula_63formula_64formula_65formula_66formula_67上記以外の状態、入力、スタック記号については常に formula_68 である。

出典:wikipedia