非決定性有限オートマトン(NFA)

nondeterministic finite automaton

「許されない遷移」があったり、「同一の状態、同一の入力記号から遷移できる状態が複数あることが許される」ように有限オートマトンを拡張することで表現力を高めて、より少ない状態数で同一の振る舞いをさせることができるようになる

「許されない遷移」をもつだけであれば「広い意味で」有限オートマトン(finite automaton)にふくめる定義もある

死状態を取り除くことができることを意味する

等価な＝同一の言語を受理する決定性有限オートマトン(finite automaton)に変換することができる。

ゆえに、NFAで受理される言語はDFAでも受理される＝正規言語(RL)である

さらにε動作を許すことでε動作をもつ非決定性有限オートマトンに拡張できる。これもDFAに変換可能である。

https://gyazo.com/1d17fd809c6a91866c69ada6a1d37051

定式化

$ M = (Q, \Sigma, \Delta, \delta, q_0, F) と表せる。

状態の有限集合$ Q

入力記号の有限集合 $ \Sigma

状態推移関数 state tranfer function $ \delta: Q \times \Sigma \longrightarrow 2^Q

初期状態 $ q_0 \in Q

最終状態 $ F