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

Nondetemernistic Finite Automaton, NFA

決定性有限オートマトンと異なり、次の状態が現在の状態の入力によって一意に決まらない

その文字列が受理状態へ辿り着く道筋が一つでも存在するなら、その文字列は受理される

複数の選択肢がある場合は推測することになるが、間違いは許されない

NFAは確実性ではなく可能性を扱う

状態数の最小化をしないなら、一つの正規表現に対して、書き方は複数ある

よね #??

自分自身に向く矢印を書く流派と書かない流派がある？

後者の場合は適当な状態を作って$ \epsilonを辿れば同じNFAにはなる

状態数は増えるけど、動き自体は同じ

例

https://gyazo.com/e88a9a35286e936db4857b42999f310b

q0のとき、'a'を受け取ったら状態遷移の可能性が複数ある

q2に来ると従うべき規則がなくなり、入力を受け付けなくなる

上の図では、「aaaaab」や「babac」などは可能性があるので受理

逆に「bbbb」などは絶対に無理なので拒否

1本の矢印には1回の遷移のみの為の文字を書く

例えばcdという正規表現だとしても、$ \circ\xrightarrow{c}\circ\xrightarrow{d}\circのように書く

正規表現はNFAに容易に変換可能 ref 『コンパイラとバーチャルマシン』.icon p.32

簡単な例題とそれを解く手順

例題: 正規表現(a|b*)cdを表す言語を受理するNFAを求めよ

https://gyazo.com/0c8d13b45e2789dfd77e274c34c4a9af

「bが0回」の場合もありうるので0から1へ$ \epsilonがある

参考