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

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

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

概要

この章は、普段僕達が使っている汎用コンピュータを
出来る限りシンプルなものにモデル化して
それをRubyでシミュレーションしていきます。

3.1 決定性有限オートマトン

有限オートマトン(finite automaton 別名:有限状態機械(finite state machine)))

理解しやすさ、推測しやすさ、実装のしやすさを得るために実際の汎用コンピュータからさまざまな機能を取り除いたモデル

ストレージもRAM存在せず、いくつかのとり得る状態と自分が今どの状態なのか
を記録する納涼を持つ

開始状態(start state)から開始し、規則(rule)に応じて入力を受け取る。
ある状態を受理状態(accept state)とし、特定の入力を受理もしくは拒否するという概念を表す。

重要なのは、このオートマトンは決定的である(deterministic)ということで、
どのような入力があっても、次の状態が決定できること。

これを決定性有限オートマトン(DFA: Deterministic Finite Automaton)と呼ぶ

3.2 非決定性有限オートマトン

DFAから決定性を取り除き、ある入力からとり得る状態が複数ある状態機械を
非決定性有限オートマトン(NFA: Nondeterministic Finite Automaton)と呼ぶ

NFAをシミュレートするには、その機械の全ての可能な実行を調べ、受理状態に
あるものがあるか、を調べる必要がある。

自由移動(free move)

何も入力を読まずに自発的に状態を変更することのできる規則。

3.4 等価性

最初に決定性有限オートマトンをシミュレートし、そこに
非決定性や自由移動を可能とすることで、複数の実行パスを可能とする
状態機械をシミュレートしてきたが、実はどんな非決定性有限オートマトンも、
まったく同じ入力を受理する決定性有限オートマトンに変換できることが
わかっている。

NFAで複数とり得る状態の集合を、DFAの状態とすることで、これをシミュレートできる。

このことから、DFAからNFAへと、何か新しい能力が備わっただけでなく
DFAで可能だったことをNFAでシンタックスシュガーとしてパッケージしただけに過ぎない。

コメントを残す

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