アンダースタンディングコンピューテーション――単純な機械から不可能なプログラムまで_読書メモ4章

4章 能力を高める

書籍の中に書かれているコードとか、より詳しい説明は極力載せません。
基本的には本の中に出てくる用語の解説等をかいつまんだ感じ・・・
興味を持っていただけたら実際に購入して読んでみることをオススメします。

※自分用メモなので内容は適当なのと、理解が進んでいくうちに追記していく可能性があります
(この記事に限らずこのブログに含まれる内容全てそうですがw)


概要

この章では前章でシミュレートしたDFA(Deterministic Finite Automaton)や
NFA(Nondeterministic Finite Automaton)にいくつかの機能を追加して、
機械の能力をあげることができないか、を検証します。


有限オートマトンの限界

例えば ((())) のような入力があり、それを正しく3回ネストしていることを
チェックする有限オートマトンは簡単にシュミレーションできるが、 n回ネストした括弧が
正しくネストしているか
という問題をチェックする有限オートマトンを設計することは
不可能。

つまり、有限オートマトンの限界とは、ある固定の状態集合という制限的なストレージしか
持っておらず、任意の情報量を記録できない。


決定性プッシュダウン・オートマトン

有限オートマトンのストレージに制限があることが問題であるなら、
そこに計算中にデータを保持できる専用の書き込みスペースを用意することを考えてみる。

ここではそのストレージとして、スタック(stack)へのアクセスを提供した機械をシミュレートする。
(Pushdown Automaton)

機械の規則が決定的である場合、この機械を決定性プッシュダウンオートマトン
(DPDA: Deterministic Pushdown Automaton)と呼ぶ


非決定性プッシュダウンオートマトン

DPDAから決定性を取り除いたものを非決定性プッシュダウンオートマトン
(NPDA:Nondeterministic Pushdown Automaton)と呼ぶ。

非等価性

DFAとNFAは、実際には等価であることを前章で確認したが、
DPDAでNPDAをシミュレートできず、非等価であることがわかっている。

NFAをDFAでシミュレートした際は、NFAでとり得る状態を集合として扱うことで
等価性を実現したが、NPDAの複数の状態のスタックをDPDAの1つのスタックで
シミュレートする方法がないため。

よって、NPDAはDPDAより能力が高い、といえる。


※NPDAの実用的な例として最期に、正規表現のパースする機械のシミュレートが
掲載されています。

どれだけ能力があるか

DPDAはDFAとNFAよりも能力が高く、NPDAは更に能力が高いことがわかった。

有限オートマトンと違って、プッシュダウンオートマトンは入力を読まずに
無限にループすることができるようになった。

DFAは入力文字を消費することでしか状態を変えられず、NFAは自由移動によって
自発的に状態を変更することができるが、最終的には有限回しか変えることができない。

これに対してPDAは1つの除隊にとどまり、同じ構成を繰り返すことなく
文字をスタックにプッシュし続けることができる。

このことからPDAがより高い能力をもった機械であることはわかった。
しかし制限として、スタックの振る舞いに大きく制限されていることが挙げられる。

第一に
スタックのトップより下にある文字にランダムアクセスすることができない。

そして、スタックのLIFOという性質により、情報を取り出す順番にも制限がある
(プッシュした順番と逆にしかスタックをの文字を消費できない)

最期に、DFA,NFA,PDAはいずれも、現実の汎用的なPCのような出力を持っておらず、
受理したか、していないかの情報しか提供できない。

つまり、汎用PCと同等の能力とは程遠いことがわかる。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です