「ぷっしゅだうん」とは?

言葉 詳細
プッシュダウン

概要 (Wikipediaから引用)

プッシュダウン・オートマトン(Pushdown Automaton)は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。 スタックのトップを使って成すべき状態遷移を判断する。 遷移実行の一部としてスタック操作を行うことが出来る。プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。 プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。