学習メモ:非決定性有限オートマトン

東京大学工学部モラトリアム養成学科の学生です。フリーでプログラマをやったりしていましたが、CSの知識は一切ありませんので、色々教えてもらえると幸いです。英語も全くネイティブではありませんが、世界標準なので使っていきます。1

読んでいく本

www.amazon.co.jp

※ 私が重要だと思った点を適当にまとめていく形になります。リファレンス的利用を想定しています。

Regular Languages

image.png

we use an idealized computer called a computational model... We begin with the simplest model ,called the finite state machine or finite automaton.

さすがにオートマトンくらい何度か聞いたことはありますが、これが全ての計算機の最小モデルなんですねー。状態遷移図の一般化みたいな感じですかね。

image.png

Formal Definition of A Finite Automaton

イメージで語っても仕方ないので、辛いですが定義を見ていきます。

f:id:mycontrib:20220112181415p:plain

Q\Sigmaがそれぞれ「状態」と「入力信号」の集合で、遷移の仕方を規定するのが関数\delta、そしてQの中で始状態q_0とaccept状態の集合Fがある感じですね。まあ必要十分という感じがします。

オートマトンには、acceptという動作があるようです。早速上記の定義が使われています。

f:id:mycontrib:20220112181649p:plain

例えば、wが文字列hogeだったらw_1hw_2oという感じに分解されて、この文字列がacceptされるかどうかは、「状態r_0から出発して、関数\deltaに現在の状態と次の入力信号を渡しながら状態を更新していき、最終的に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 L(M)=A. We say that M recognizes A.

ちょっと最初この文章がしっくり頭に入ってこなかったんですが、どうも状態遷移図のような先入観はあんまり良くないですね。

オートマトンは状態遷移図のようにただ遷移の様子を分かりやすく表すことが目的というよりは、「入力信号を分解してacceptか否かに振り分ける」ということで、どちらかというと正規表現って感じです。

(→正規表現と有限オートマトンは同値のようです。直感的には当然ですね。)

NFA; Nondeterministic Finite Automata

image.png

非決定性有限オートマトン(NFA)ですね。ちなみに決定性有限オートマトンDFAです。

1. 1つの状態からの各alphabetに対応する矢印数が0~複数
2. [tex:\epsilon]という自動で遷移する特殊なラベルが追加

という2点で拡張がなされています。あくまで拡張なので決定性オートマトンも非決定性の一部という感じのようですねー。2

形式的な定義は以下になります。

f:id:mycontrib:20220112181950p:plain

DFAと比べて変化しているのは3番のみです。\Sigma_{\epsilon}\Sigma\cup\{\epsilon\}を、P(Q)Qの全てのsubsetの集合をそれぞれ示しています。

先ほど述べた、「1. 1つの状態からの各alphabetに対応する矢印数が0~複数」は値域のP(Q)、「2. \epsilonという自動で遷移する特殊なラベルが追加」は定義域の\Sigma_{\epsilon}に反映されているということですね。

実は全てのNFAは同等の(同じ言語を認識する)DFAに変換できるということですが、以上述べた非決定性の拡張によって、多くのオートマトンの表現が簡潔になるようです。

役割分担

image.png

"language"は集合であることに注意していきます。Aはバイナリの中で「末尾から3番目に1がくる」文字列の集合のようです。これを認識するには、1を検知して、その次に2つのみ0または1が続いて終了すればacceptしたいということです。

厄介なのは、最初に検知した1の次にくる文字になります。例えば、"110"ときてその後にもう一度"0"が来た場合、最初の1は末尾から4番目になって候補から外れますが、その隣の1は候補に入っているわけです。

この手順をシンプルに表現するには、検知した複数の1を独立に評価できると良さそうです。そこで、上図では入力が0でも1でもq_1に居続けながら、1だった場合はその都度分岐して2文字後に終わるかどうかチェックする手筈になっているわけですね。

ちなみに、上記のNFAをDFAで書き換えると以下のようになるようです。 うーん、コードでもいつの間にこんな書き方になってることある!気をつけたいです。

image.png

Every NFA has an equivalent DFA.

次はより一般的に、NFAからDFAへの変換を行なっていきます。

Let N=(Q, \Sigma, \delta, q_0, F) be the NFA recognizing some language A. We construct a DFA M=(Q^{'}, \Sigma, \delta^{'}, q_0^{'}, F^{'}) recognizing A.

:::note 準備として、εを考慮するためにちょっとした関数を用意します。 :::

For R\subseteq Q let E(R)=\{q;q can be reached from R by traveling along 0 or more \epsilon arrows\}.

それでは実際にDFAを構築していきます。なお、入力集合\Sigmaは同じですので、残りの4つを扱います。

  1. Q^{'}=P(Q).
  2. \delta^{'}(R,a)=\bigcup_{r\in R}E(\delta(r,a))\text{ for }R\in Q^{'}\text{ and }a\in\Sigma.
  3. q_0^{'}=E(\{q_0\}).
  4. F^{'}=\{R\in Q^{'};R\text{ contains an accept state of }N\}.

ここら辺で皆さんが置いていかれないように(訳:私が適当にスルーしてしまわないように)丁寧に進んでいきます。

まずQ^{'}は状態集合でした。NFAでは複数の状態を同時に取ることができます。例えばq_1q_2の両方にいるという「状況」をDFAで表現するためには、\{q_1,q_2\}という部分集合を1つの「状態」として扱う必要があります。従って、状態集合としては、それらの部分集合の集合であるP(Q)となります。

次に、\delta^{'}は「現在の状態と次の入力信号を受けて次の状態を返す」関数でした。 NFAでは、「1~複数の状態から、それぞれが1つのalphabetを受けて0~複数の状態へ遷移、さらに遷移後に\epsilon矢があればさらにその先へ分岐遷移」という形をとります。これが構築中のDFAの場合は、引数R\in Q^{'}=P(Q)がそれ自体部分集合になっていて0~複数の状態を表せます。戻り値は、その部分集合Rの各要素状態rを個別にNFAの\deltaにかけて、さらに\epsilonのためにEをかませてから論理和をとったものになっています(適当にイメージを描いてみた↓)。

image.png

次のq_0^{'}は素直ですね。状態集合Q^{'}=P(Q)に合わせq_0を集合にし、\epsilonがあったら事前に遷移させます。

最後のF^{'}は、部分集合の1つでも元のNFAでacceptであれば良いということで、直接的な定義になっていますね。

Closure Under The Regular Operations

NFAをうまく扱えば、正規言語3の性質も容易に示すことができるようです。

f:id:mycontrib:20220112182548p:plain

※ もう一度書きますが、"language"は「集合」です(あるオートマトンが受理する全ての文字列の集合)。

例えば、正規言語がこれらの操作に閉じている(これらの操作後もregularである4)ことが示せます。

Union

image.png

上記の構成でN_1A_1を、N_2A_2を認識するとき、NA_1\cup A_2を認識(その集合の要素を全てaccept)します。Nの形式的な構成も書いてみます。

  1. Q=\{q_0\}\cup Q_1\cup Q_2
  2. q_0 is the start state of N
  3. F=F_1\cup F_2 4. 

\delta(q,a)= 
     \begin{cases}
       \delta_1(q,a)\text{,} &\quad\text{if }q\in Q_1\\
       \delta_2(q,a)\text{,} &\quad\text{if }q\in Q_2\\
       \{q_1,q_2\} &\quad\text{if }q=q_0\text{ and }a=\epsilon\\
       \emptyset\text{,} &\quad\text{if }q=q_0\text{ and }a\neq\epsilon.\\
     \end{cases}

Concatenation

image.png

N_1のaccept状態をただのstateに戻し、そこから続けてN_2をacceptするかチェックしています。N_1で一度accept状態になったとしても、そこからN_1の別のaccept状態に移ったりすることも考えられるので、\epsilonによる分岐が必要になりますね。

  1. Q=Q_1\cup Q_2
  2. q_0=q_1
  3. F=F_2 4. 

\delta(q,a)= 
     \begin{cases}
       \delta_1(q,a)\text{,} &\quad\text{if }(q\in Q_1\text{ and }q\notin F_1)\text{ or }(q\in F_1\text{ and }a\neq\epsilon)\\
       \delta_1(q,a)\cup\{q_2\}\text{,} &\quad\text{if }q\in F_1\text{ and }a=\epsilon\\
       \delta_2(q,a)\text{,} &\quad\text{if }q\in Q_2.\\
     \end{cases}

Star

image.png

k=0ならばA^*=\emptysetとなるので、始状態をacceptにして、入力が始まればそこは死んでN_1部分のみ動くようになってますね。そこから任意のN_1のacceptを任意の回数連続させたものを認識できるようになっているようです。

  1. Q=\{q_0\}\cup Q_1
  2. q_0 is the start state of N
  3. F=\{q_0\}\cup F_1 4. 
  
\delta(q,a)= 
     \begin{cases}
       \delta_1(q,a)\text{,} &\quad\text{if }(q\in Q_1\text{ and }q\notin F_1)\text{ or }(q\in F_1\text{ and }a\neq\epsilon)\\
       \delta_1(q,a)\cup\{q_1\}\text{,} &\quad\text{if }q\in F_1\text{ and }a=\epsilon\\
       \{q_1\}\text{,} &\quad\text{if }q=q_0\text{ and }a=\epsilon.\\
       \emptyset\text{,} &\quad\text{if }q=q_0\text{ and }a\neq\epsilon.\\
     \end{cases}

  1. 真面目に話すと、大学のライセンスにより無償で読めてしまうものが多いからです。うちの人はここから。あと古い本は結構海外の大学ドメインでpdf公開してたりしますが、その辺は自己判断で。

  2. ていうか今更ですけどこれって「ソフトウェア」の最小モデルってことなんですかね?(論理回路、順序回路とかの方が「計算機の最小モデル」っぽい感じがしてしまいました)

  3. であってるのかな?

  4. 書き忘れましたが"regularである"の定義は"acceptする有限オートマトンが存在する"です。