プッシュダウン・オートマトン
 | この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。 |
プッシュダウン・オートマトン（英: pushdown automaton, PDA）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。
ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。
概要
プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。
- スタックのトップを使って成すべき状態遷移を判断する。
- 遷移実行の一部としてスタック操作を行うことが出来る。
プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。
プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。スタック操作とはある特定の文字をスタックにプッシュすることやスタックのトップをポップすることを意味する。また、プッシュダウン・オートマトンはスタックを操作せずにそのままにしておくこともできる。どう操作するかは状態遷移表によって決定される。
まとめると、入力信号と現在状態とスタック上の文字によって状態遷移すると共に、必要に応じてスタック操作を行う。
有限オートマトンでも特に非決定性有限オートマトンに基づいている場合、「非決定性プッシュダウン・オートマトン」（NPDA、nondeterministic pushdown automaton）と呼ばれる。決定性有限オートマトンに基づいている場合、「決定性プッシュダウン・オートマトン」（DPDA、deterministic pushdown automaton）と呼ばれる。非決定性とは、入力信号と状態とスタック上の文字を与えられても次の遷移先が一意に決定されない場合があることを意味する。
有限オートマトンにふたつのスタックを接続することもでき、これは事実上チューリングマシンと等価な非常に強力なデバイスとなる。線形拘束オートマトンはプッシュダウン・オートマトンよりも強力だが、チューリングマシンよりは非力である。
形式的定義
形式的には、PDA は以下の6-タプルで定義される。
- Pushdown automatonのページへのリンク
