kanachi-blog
正規表現早見表
正規表現を受理するNFAとDFA
共通点
- 有限オートマトン（finite automaton）の一種で、正規言語を受理する。
- 現在の状態と入力記号に応じて、次の状態に移行する。
- 終了状態（受理状態）を持ち、受理された場合は真（True）を返す。
NFA
- 現在の状態と入力記号に対して、複数の次の状態に移行できることがある。
- 空文字（ε）を受け付けることができる。
- 受理状態に到達するまで、全ての入力記号を消費する必要はない。
- 探索が必要で計算量大
- NFA→DFAには変換可能
DFA
- 全ての状態から、同じ入力記号に対しては同じ状態に移行することが決定されている。
- 1つの入力記号に対して1つの状態にしか移行しない。
- 受理状態に到達するまで、全ての入力記号を消費する必要がある。
- 構築に計算量大、メモリ大だが、探索は不要なので実行はO(n) と高速
