Nondetemernistic Finite Automaton, NFA

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

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

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

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

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

よね #??

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

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

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

例

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

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

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

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

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

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

正規表現はNFAに容易に変換可能 ref p.32

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

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

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

参考