この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。(2023年1月) オートマトン理論 プッシュダウン・オートマトン(英: pushdown automaton, PDA)は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 概要[編集] プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。 スタックのトップを使って成すべき状態遷移を判断する。 遷移実行の一部としてスタック操作を行うことが出来る。 プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オー
![プッシュダウン・オートマトン - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/33c0df4e847b35dc9a4a4be474ef62c1e7efde8b/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2Fa%2Fa2%2FAutomata_theory.svg%2F1200px-Automata_theory.svg.png)