うさぎでもわかるオートマトンと言語理論　第02羽　非決定性オートマトン(NFA)の書き方・決定性オートマトン(DFA)への変換

2019年8月28日 2019年8月28日 12分49秒

ももうさ

スポンサードリンク

こんにちは、ももやまです。

前回は決定性オートマトン(DFA)について説明しました。

今回は決定性ではないオートマトン、非決定性オートマトン(NFA)についてまとめていきたいと思います。

前回の決定性オートマトン（第01羽）についての記事はこちらから！

www.momoyama-usagi.com

目次 [hide]

１．非決定性オートマトン(NFA)と決定性オートマトン(DFA)の2つの違い
- その1　状態遷移が1本道でなくてもOK
- その2　初期状態が2つ以上あってもOK
２．非決定性オートマトンを書いてみよう
- 例題1
- 解説1
３．非決定性オートマトンの状態遷移表
- 例題2
- 解説2
４．非決定性オートマトン(NFA)から決定性オートマトン(DFA)の変換
５．練習問題
- 練習1
- 練習2
６．練習問題の答え
- 解答1
- 解答2
７．さいごに

スポンサードリンク

１．非決定性オートマトン(NFA)と決定性オートマトン(DFA)の2つの違い

非決定性オートマトンは、決定性オートマトンと違う点を2つ持っています。

その1　状態遷移が1本道でなくてもOK

決定性オートマトンは、状態遷移図のたどり方が必ず1本道でしたね。

一方、非決定性オートマトンでは、状態遷移図のたどり方が1本道ではなくてもOKです！

その2　初期状態が2つ以上あってもOK

前回の決定性オートマトンの説明で、初期状態（スタート地点）は必ず1つと説明しましたね。

一方、非決定性オートマトンでは、初期状態が2つ以上設定することもOKです！
なので、このように状態遷移図を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。

スポンサードリンク

３．非決定性オートマトンの状態遷移表

決定性オートマトンと異なり、非決定性オートマトンの場合は遷移先が2つ以上になったり、1つもないことがあります。そのため、状態遷移を把握するのが決定性に比べて少しめんどくさいです。

そのため、状態遷移表を書くことで状態遷移を把握しやすくします。

では、非決定性オートマトンの状態遷移表の書き方について例題を2つほど踏まえながら説明していきましょう。

例題2

つぎの(1), (2)の状態遷移図で表される非決定性オートマトンの状態遷移表を書きなさい。

(1)

(2)

解説2

(1)

初期状態は $q_{0}$ ですね。
まずは、初期状態から遷移可能な場所を $a$ のとき、 $b$ のときに場合分けして考えましょう。

$a$ のとき： $q_{0}$ , $q_{1}$ の2箇所に遷移可能
$b$ のとき： $q_{0}$ に遷移可能

$a$ , $b$ それぞれの動き（遷移可能場所）がわかったので $q_{0}$ のときの動きを状態遷移図に記録します。

ここで新たに生成された $q_{0}$ と $q_{1}$ の2状態が含まれた状態 ${q_{0}, q_{1}}$ について考えましょう。

${q_{0}, q_{1}}$ には、受理状態である $q_{1}$ が含まれていますね。このように、複数状態含まれた中に1状態でも受理状態が含まれる場合、複数状態をもつ状態も受理状態となります。

なので、 ${q_{0}, q_{1}}$ も受理状態となります。赤色などの別の色に着色するか、○印などの記号をつけておきましょう。

今度は状態 ${q_{0}, q_{1}}$ が遷移できる場所を $a$ のとき $b$ のときで場合分けしましょう。

複数状態の場合、それぞれの状態から遷移可能なすべての状態を考えます。

$a$ のとき： $q_{0}$ からは $q_{0}$ , $q_{1}$ の2箇所に遷移可能、 $q_{1}$ からはどこも遷移できない。よって $q_{0}$ , $q_{1}$ の2箇所に遷移可能。

$b$ のとき： $q_{0}$ からは $q_{0}$ に遷移可能。 $q_{1}$ からはどこも遷移できない。よって $q_{0}$ から遷移可能。

$a$ , $b$ のときの遷移先がわかったので ${q_{0}, q_{1}}$ のときの動きを状態遷移図に記録します。

これですべての状態を調べおわりましたね。状態遷移表の完成です！

今回は2状態でしたが、実際は未知の状態が出てこなくなるまで調べる必要があるため、かなりの状態数となってしまうこともあります。

(2)

初期状態は $q_{0}$ ですね。
(1)と同じように初期状態から遷移可能な場所を $a$ のとき、 $b$ のときに場合分けして考えましょう。

$a$ のとき： $q_{1}$ に遷移可能
$b$ のとき：どこにも遷移できない

$b$ のときの遷移先がないため、空の状態 $ϕ$ となります。、空状態も1つの状態として考えてください。

ここで、 $q_{1}$ と $ϕ$ という未知の遷移が2つ出てきましたね。

この2つの遷移先を調べてみましょう。

$q_{1}$ の遷移先

$a$ のとき：どこにも遷移できない
$b$ のとき： $q_{0}$ に遷移可能

こちらも $a$ のときはどこにも遷移できず、空状態 $ϕ$ となってしまいます。

$q_{1}$ の状態遷移を表に記録すると、

となります。

最後に空状態ですが、空状態にどんな文字を入れてもどの状態にもいけません。なので、空状態 $ϕ$ からは $a$ , $b$ どちらの文字を入れても空状態 $ϕ$ となります。よって、

となります。

このように複数先の遷移をする状態やどこにも遷移しない空の状態も1つの状態として考えることにより、それぞれの状態と文字による遷移先を明確に表すことができます。

４．非決定性オートマトン(NFA)から決定性オートマトン(DFA)の変換

先ほど非決定性オートマトンを状態遷移表にする練習をしましたね。

実は、状態遷移表にすることで、それぞれの状態と次の文字に対する遷移先が1つに表すことができます。

すべての非決定性オートマトンで状態遷移表を書くことができるので、非決定性オートマトンで表すことができるオートマトンは、決定性オートマトンでも表すことができます！*1

例題2(1)の非決定性オートマトンを思い出して見ましょう。

この非決定性オートマトンを状態遷移表にし、変数名を簡単にする*2と……

[2021/04/20 訂正]

状態遷移図の遷移先（矢印）が誤ったものになっていたため、訂正を行いました。申し訳ございません。

このように、決定性オートマトンに変換することができます！
（状態遷移表→状態遷移図は表を見ながらミスせずに矢印を書くだけなので解説省略します。）

例題2(2)の非決定性オートマトンも……

このように非決定性の状態遷移表を記述することで簡単に決定性オートマトンに変換することができます！

※ 空状態 $ϕ$ は現状態からどこにもいけないようなときのみ使用することをおすすめします。

例えば現状態が ${1, 2}$ で状態1からは3に遷移できるけど状態2からはどこにも遷移できないとき、 ${3, ϕ}$ ではなく ${3}$ としましょう。（状態数が増えてしまうので…）

５．練習問題

では、少しだけですが練習をしてみましょう。

練習1

$Σ = {a, b}$ とする。

$a$ が1文字以上続いたあとに $b$ が1文字以上続くような文字列を受理するような言語 $L$ 、 $L = {a^{i} b^{j} | i ≧ 1, j ≧ 1}$ について次の(1), (2)の問いに答えなさい。

(1) $L$ を受理する非決定性オートマトンを求めなさい。
(2) (1)の状態遷移表を書くことにより、 $L$ を受理する決定性オートマトンを求めなさい。

練習2

$Σ = {0, 1}$ とする。
つぎの(1), (2)で表されている非決定性オートマトンを決定性オートマトンに直しなさい。

(1)

(2)

６．練習問題の答え

解答1

(1)

$a$ が1回続いてから、 $b$ が1回以上続くような非決定性オートマトンは、下のように書ける。

（最初に $b$ が来たり、abbbabのように $b$ のあとに $a$ が来るような文字列は受理しないことに注意）

(2)

(1)で書いたオートマトンの状態遷移表を書き、変数名を簡単にする。受理状態が3、初期状態が1であることを忘れずに。
（現状態にかかれている2桁の数、12は状態1、状態2が両方含まれる状態を指す。カッコを書くのがめんどくさいため、省略した。また、状態9は空の状態、Dead state、あり地獄を表す。）