計算機科学
computation

有限オートマトン/プッシュダウン・オートマトン/チューリングマシンの違い

More than 1 year has passed since last update.

『アンダースタンディング コンピュテーション』 より、自分用メモ。


Type
有限オートマトン
プッシュダウン・オートマトン
チューリングマシン

英名
Finite Automaton(FA)
Push-Down Automaton(PDA)
Turing Machine(TM)

外部ストレージ


状態管理       
内部状態
スタック
無限の長さのテープ(または1次元配列)

決定性と非決定性の等価性
○(等価)
☓(非決定性のほうが能力が高い)
○(等価)

有限性
あり
なし(スタックに状態を動的に追加)
なし(テープに状態を動的に追加)

具体例(本書中)
正規表現
字句解析・構文解析
2進数のインクリメント・文字列認識