NFA
正式名称
Nondeterministic Finite Automaton（非決定性有限オートマトン）
一言でいうと
同じ入力から複数の状態へ遷移できる有限オートマトン
初心者向け説明
NFAとは、ある状態で同じ入力を受け取ったときに、複数の状態へ遷移できる有限オートマトンです。
例えば、
┌→ q1
q0 --a--|
└→ q2
のように、q0でaを入力したとき、q1またはq2へ進める場合があります。
複数の経路がある場合、その中の少なくとも1つが入力終了時に受理状態へ到達すれば、その文字列は受理されます。
ポイント
- 非決定性有限オートマトンとも呼ばれる
- 同じ入力で複数の遷移先を持てる
- ε遷移を持つ場合がある
関連用語
関連記事
- オートマトンとは？状態遷移図・有限オートマトン・DFAとNFAを基礎から理解しよう
🍯 はちみつメモ
NFA = 同じ入力でも複数の遷移先を持つことができる