|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ マトン ： [まとん] (n) mutton, (n) mutton
プッシュダウン・オートマトン（''Pushdown Automaton''）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 == 概要 == プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。 #スタックのトップを使って成すべき状態遷移を判断する。 #遷移実行の一部としてスタック操作を行うことが出来る。 プッシュダウン・オートマトンは入力信号、現在状態、スタックのトップを使って状態遷移表内の位置を指定することで遷移先を選択する。通常の有限オートマトンは現在状態と入力信号しかなく、スタックは持たない。プッシュダウン・オートマトンはスタックを遷移先選択のパラメータに加える。つまり、入力信号と現在状態とスタックのトップにある文字から遷移先を選択する。 プッシュダウン・オートマトンは、遷移を実行する動作の一部としてスタックを操作することもできる。通常の有限オートマトンは遷移の結果として新しい状態を選択する。スタック操作とはある特定の文字をスタックにプッシュすることやスタックのトップをポップすることを意味する。また、PDAはスタックを操作せずにそのままにしておくこともできる。どう操作するかは状態遷移表によって決定される。 まとめると、入力信号と現在状態とスタック上の文字によって状態遷移すると共に、必要に応じてスタック操作を行う。 有限オートマトンでも特に非決定性有限オートマトンに基づいている場合、「非決定性プッシュダウン・オートマトン」（NPDA）と呼ばれる。決定性有限オートマトンに基づいている場合、「」（DPDA）と呼ばれる。非決定性とは、入力信号と状態とスタック上の文字を与えられても次の遷移先が一意に決定されない場合があることを意味する。 有限オートマトンにふたつのスタックを接続することもでき、これは事実上チューリングマシンと等価な非常に強力なデバイスとなる。線形拘束オートマトンはプッシュダウン・オートマトンよりも強力だが、チューリングマシンよりは非力である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「プッシュダウン・オートマトン」の詳細全文を読む スポンサード リンク
|