
スポンサードリンク
こんにちは、ももやまです。
前回は決定性オートマトン(DFA)について説明しました。
今回は決定性ではないオートマトン、非決定性オートマトン(NFA)についてまとめていきたいと思います。
前回の決定性オートマトン(第01羽)についての記事はこちらから!
目次 [hide]
スポンサードリンク
1.非決定性オートマトン(NFA)と決定性オートマトン(DFA)の2つの違い
非決定性オートマトンは、決定性オートマトンと違う点を2つ持っています。
その1 状態遷移が1本道でなくてもOK
決定性オートマトンは、状態遷移図のたどり方が必ず1本道でしたね。
一方、非決定性オートマトンでは、状態遷移図のたどり方が1本道ではなくてもOKです!
その2 初期状態が2つ以上あってもOK
前回の決定性オートマトンの説明で、初期状態(スタート地点)は必ず1つと説明しましたね。
一方、非決定性オートマトンでは、初期状態が2つ以上設定することもOKです!
なので、このように状態遷移図を2つに分けることもできます!
以上の2つの違いから、非決定性オートマトンは決定性オートマトンに比べてより直感的なオートマトンの記述が可能です!
スポンサードリンク
2.非決定性オートマトンを書いてみよう
では、非決定性オートマトンを書く練習をすることで、より直感的にオートマトンを記述できることを体感してもらいましょう。
例題1
つぎの(1), (2)の条件を満たすような文字列を受理するような非決定性オートマトンの状態遷移図を書きなさい。
(1) 00で始まる文字列を受理するもの。
(2) 2文字以上の文字列で、文字列の始点と終点が異なるような文字列を受理するもの。
(受理例:00111→始点は0、終点は1なので受理 1000→始点は1、終点は0なので受理)
(非受理例:1→2文字以上ないため拒否 01010→始点が0、終点が0なので拒否)
解説1
(1)
00で始まる文字列ということは、最初の2文字が0,0であれば残りはどんな文字であっても受理するようなオートマトンとなる。
つまり、
となる。
(2)
文字列の始点と終点が異なるようなものを受理するためには、0で始まって1で終わるも文字列もしくは1で始まって0で終わる文字列を受理させればよい。
つまり、「0で始まって1で終わるものを受理する非決定性オートマトン」と「1で始まって0で終わるものを受理する非決定性オートマトン」を2つセットで書けばよい。
と書ける。
もちろん1つにまとめて
と書いてもOK。
スポンサードリンク
3.非決定性オートマトンの状態遷移表
決定性オートマトンと異なり、非決定性オートマトンの場合は遷移先が2つ以上になったり、1つもないことがあります。そのため、状態遷移を把握するのが決定性に比べて少しめんどくさいです。
そのため、状態遷移表を書くことで状態遷移を把握しやすくします。
では、非決定性オートマトンの状態遷移表の書き方について例題を2つほど踏まえながら説明していきましょう。
例題2
つぎの(1), (2)の状態遷移図で表される非決定性オートマトンの状態遷移表を書きなさい。
(1)
(2)
解説2
(1)
初期状態は
まずは、初期状態から遷移可能な場所を
ここで新たに生成された
なので、
今度は状態
複数状態の場合、それぞれの状態から遷移可能なすべての状態を考えます。
これですべての状態を調べおわりましたね。状態遷移表の完成です!
今回は2状態でしたが、実際は未知の状態が出てこなくなるまで調べる必要があるため、かなりの状態数となってしまうこともあります。
(2)
初期状態は
(1)と同じように初期状態から遷移可能な場所を
ここで、
この2つの遷移先を調べてみましょう。
こちらも
となります。
最後に空状態ですが、空状態にどんな文字を入れてもどの状態にもいけません。なので、空状態
となります。
このように複数先の遷移をする状態やどこにも遷移しない空の状態も1つの状態として考えることにより、それぞれの状態と文字による遷移先を明確に表すことができます。
4.非決定性オートマトン(NFA)から決定性オートマトン(DFA)の変換
先ほど非決定性オートマトンを状態遷移表にする練習をしましたね。
実は、状態遷移表にすることで、それぞれの状態と次の文字に対する遷移先が1つに表すことができます。
すべての非決定性オートマトンで状態遷移表を書くことができるので、非決定性オートマトンで表すことができるオートマトンは、決定性オートマトンでも表すことができます!*1
例題2(1)の非決定性オートマトンを思い出して見ましょう。
この非決定性オートマトンを状態遷移表にし、変数名を簡単にする*2と……
[2021/04/20 訂正]
状態遷移図の遷移先(矢印)が誤ったものになっていたため、訂正を行いました。申し訳ございません。
このように、決定性オートマトンに変換することができます!
(状態遷移表→状態遷移図は表を見ながらミスせずに矢印を書くだけなので解説省略します。)
例題2(2)の非決定性オートマトンも……
このように非決定性の状態遷移表を記述することで簡単に決定性オートマトンに変換することができます!
※ 空状態
例えば現状態が
5.練習問題
では、少しだけですが練習をしてみましょう。
練習1
(1)
(2) (1)の状態遷移表を書くことにより、
練習2
つぎの(1), (2)で表されている非決定性オートマトンを決定性オートマトンに直しなさい。
(1)
(2)
6.練習問題の答え
解答1
(1)
(最初に
(2)
(1)で書いたオートマトンの状態遷移表を書き、変数名を簡単にする。受理状態が3、初期状態が1であることを忘れずに。
(現状態にかかれている2桁の数、12は状態1、状態2が両方含まれる状態を指す。カッコを書くのがめんどくさいため、省略した。また、状態9は空の状態、Dead state、あり地獄を表す。)
あとは作成した状態遷移表をもとに状態遷移図を書けばよい。
となる。
解答2
(1)
下のように状態遷移表を書いてから状態遷移図に変形すればいい。
(図の12は状態1と状態2が両方含まれる状態、123は状態1、状態2、状態3がすべて含まれる状態を表す。)
実は、状態3と状態4はとある方法を使うと1つにまとめることもできますが、まとめる方法はまた別の機会に紹介します。
(2)
状態が増えてきたら、それぞれの状態から各文字における遷移先を下のようにメモしておくとミスが減らせるかもしれません。
1 → 0: 2 1: 9
2 → 0: 9 1: 13
3 → 0: 3 1: 4
4 → 0: 3 1: 4
9 → 0: 9 1: 9
初期値が2つあることに注意してください。
(1)と同じように2桁以上の数字で表された状態は、複数の状態を表しています。)
状態遷移表より、状態遷移図は以下のようになる。
(色はわかりやすくするためにつけているだけです)
7.さいごに
今回は、非決定性オートマトン(NFA)の書き方、非決定性オートマトン(NFA)を決定性オートマトン(DFA)に変換する方法についてまとめました。
非決定性オートマトンで表すことのできるものは必ず決定性オートマトンに直すことができるので、決定性オートマトンが書くのが難しいなと思った人は、最初に直感的に書きやすい非決定性オートマトンを求めてから決定性オートマトンに変換するのをおすすめします。
Next「第03羽」はこちら!↓
関連広告・スポンサードリンク