学習メモ:非決定性有限オートマトン
東京大学工学部モラトリアム養成学科の学生です。フリーでプログラマをやったりしていましたが、CSの知識は一切ありませんので、色々教えてもらえると幸いです。英語も全くネイティブではありませんが、世界標準なので使っていきます。1
読んでいく本
※ 私が重要だと思った点を適当にまとめていく形になります。リファレンス的利用を想定しています。
Regular Languages
we use an idealized computer called a computational model... We begin with the simplest model ,called the finite state machine or finite automaton.
さすがにオートマトンくらい何度か聞いたことはありますが、これが全ての計算機の最小モデルなんですねー。状態遷移図の一般化みたいな感じですかね。
Formal Definition of A Finite Automaton
イメージで語っても仕方ないので、辛いですが定義を見ていきます。
とがそれぞれ「状態」と「入力信号」の集合で、遷移の仕方を規定するのが関数、そしての中で始状態とaccept状態の集合がある感じですね。まあ必要十分という感じがします。
オートマトンには、acceptという動作があるようです。早速上記の定義が使われています。
例えば、が文字列hoge
だったらはh
、はo
という感じに分解されて、この文字列がacceptされるかどうかは、「状態から出発して、関数に現在の状態と次の入力信号を渡しながら状態を更新していき、最終的にaccept状態のいずれかにあるか否か」ということですね。
オートマトンは正規表現
automaton, acceptなどが分かったところで、次の定義を見ていきます。
If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write . We say that M recognizes A.
ちょっと最初この文章がしっくり頭に入ってこなかったんですが、どうも状態遷移図のような先入観はあんまり良くないですね。
オートマトンは状態遷移図のようにただ遷移の様子を分かりやすく表すことが目的というよりは、「入力信号を分解してacceptか否かに振り分ける」ということで、どちらかというと正規表現って感じです。
(→正規表現と有限オートマトンは同値のようです。直感的には当然ですね。)
NFA; Nondeterministic Finite Automata
非決定性有限オートマトン(NFA)ですね。ちなみに決定性有限オートマトンはDFAです。
1. 1つの状態からの各alphabetに対応する矢印数が0~複数 2. [tex:\epsilon]という自動で遷移する特殊なラベルが追加
という2点で拡張がなされています。あくまで拡張なので決定性オートマトンも非決定性の一部という感じのようですねー。2
形式的な定義は以下になります。
DFAと比べて変化しているのは3番のみです。はを、はの全てのsubsetの集合をそれぞれ示しています。
先ほど述べた、「1. 1つの状態からの各alphabetに対応する矢印数が0~複数」は値域の、「2. という自動で遷移する特殊なラベルが追加」は定義域のに反映されているということですね。
実は全てのNFAは同等の(同じ言語を認識する)DFAに変換できるということですが、以上述べた非決定性の拡張によって、多くのオートマトンの表現が簡潔になるようです。
役割分担
"language"は集合であることに注意していきます。はバイナリの中で「末尾から3番目に1がくる」文字列の集合のようです。これを認識するには、1を検知して、その次に2つのみ0または1が続いて終了すればacceptしたいということです。
厄介なのは、最初に検知した1の次にくる文字になります。例えば、"110"ときてその後にもう一度"0"が来た場合、最初の1は末尾から4番目になって候補から外れますが、その隣の1は候補に入っているわけです。
この手順をシンプルに表現するには、検知した複数の1を独立に評価できると良さそうです。そこで、上図では入力が0でも1でもに居続けながら、1だった場合はその都度分岐して2文字後に終わるかどうかチェックする手筈になっているわけですね。
ちなみに、上記のNFAをDFAで書き換えると以下のようになるようです。 うーん、コードでもいつの間にこんな書き方になってることある!気をつけたいです。
Every NFA has an equivalent DFA.
次はより一般的に、NFAからDFAへの変換を行なっていきます。
Let be the NFA recognizing some language . We construct a DFA recognizing .
:::note 準備として、εを考慮するためにちょっとした関数を用意します。 :::
For let can be reached from by traveling along 0 or more arrows.
それでは実際にDFAを構築していきます。なお、入力集合は同じですので、残りの4つを扱います。
- .
- .
- .
- .
ここら辺で皆さんが置いていかれないように(訳:私が適当にスルーしてしまわないように)丁寧に進んでいきます。
まずは状態集合でした。NFAでは複数の状態を同時に取ることができます。例えばとの両方にいるという「状況」をDFAで表現するためには、という部分集合を1つの「状態」として扱う必要があります。従って、状態集合としては、それらの部分集合の集合であるとなります。
次に、は「現在の状態と次の入力信号を受けて次の状態を返す」関数でした。 NFAでは、「1~複数の状態から、それぞれが1つのalphabetを受けて0~複数の状態へ遷移、さらに遷移後に矢があればさらにその先へ分岐遷移」という形をとります。これが構築中のDFAの場合は、引数がそれ自体部分集合になっていて0~複数の状態を表せます。戻り値は、その部分集合の各要素状態を個別にNFAのにかけて、さらにのためにをかませてから論理和をとったものになっています(適当にイメージを描いてみた↓)。
次のは素直ですね。状態集合に合わせを集合にし、があったら事前に遷移させます。
最後のは、部分集合の1つでも元のNFAでacceptであれば良いということで、直接的な定義になっていますね。
Closure Under The Regular Operations
NFAをうまく扱えば、正規言語3の性質も容易に示すことができるようです。
※ もう一度書きますが、"language"は「集合」です(あるオートマトンが受理する全ての文字列の集合)。
例えば、正規言語がこれらの操作に閉じている(これらの操作後もregularである4)ことが示せます。
Union
上記の構成でがを、がを認識するとき、はを認識(その集合の要素を全てaccept)します。の形式的な構成も書いてみます。
- is the start state of
- 4.
Concatenation
のaccept状態をただのstateに戻し、そこから続けてをacceptするかチェックしています。で一度accept状態になったとしても、そこからの別のaccept状態に移ったりすることも考えられるので、による分岐が必要になりますね。
- 4.
Star
ならばとなるので、始状態をacceptにして、入力が始まればそこは死んで部分のみ動くようになってますね。そこから任意ののacceptを任意の回数連続させたものを認識できるようになっているようです。
- is the start state of
- 4.