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

非決定性有限オートマトン（NFA）とは

非決定性有限オートマトン（NFA: Nondeterministic Finite Automaton）とは、有限オートマトンの一種であり、ある状態と入力があった際に、次の遷移先が一意に定まらない可能性があるものを指します。これは、決定性有限オートマトン（DFA）とは対照的な特徴です。

NFAの直感的な説明

NFAは、入力文字列を読み込みながら状態を遷移していきます。各入力文字を読み込むたびに、現在の状態から複数の状態へ同時に遷移する可能性があり、どの遷移が正しいかは後続の入力によって決定されます。このプロセスは全ての入力文字が読み込まれるまで継続されます。

非決定性の要素

NFAが「非決定性」と呼ばれる理由は以下の2点にあります。

1. 遷移先の不定性: ある状態と入力文字が与えられたとき、遷移先が一つに定まらない場合があります。複数の状態への遷移が同時に起こり得ます。
2. イプシロン遷移: 入力文字を受け取らずに状態遷移が可能な場合があります。これは「イプシロン遷移（ε-遷移）」と呼ばれ、状態遷移図ではεで示されます。

受容と拒否

NFAが入力文字列を読み終えた際、少なくとも一つの遷移経路が受容状態に到達すれば、その入力文字列はNFAによって「受容された」とみなされます。逆に、全ての遷移経路が受容状態に到達しない場合は、その文字列は「拒否された」と判断されます。

NFAの形式的な定義

NFAは、以下の5つの要素で定義されます。

S: 状態の有限集合
Σ: 入力文字の有限集合
T: 遷移関数 `T: S × (Σ ∪ {ε}) → P(S)`
s₀: 初期状態 `s₀ ∈ S`
A: 受容状態の集合 `A ⊆ S`

ここで、`P(S)`はSの冪集合、εは空文字列を表します。

NFAによる文字列の受容

NFA `M = (S, Σ, T, s₀, A)` が文字列 `X` を受容する条件は以下の通りです。

文字列 `X` を `x₁, x₂, ..., xₙ` （各 `xᵢ` は `Σ ∪ {ε}` の要素）と表したとき、状態遷移の系列 `r₀, r₁, ..., rₙ` が存在し、以下の条件を満たす必要があります。

1. `r₀ = s₀` （初期状態は `s₀` である）
2. `rᵢ ∈ T(rᵢ₋₁, xᵢ)` (各ステップで、遷移関数に従って遷移)
3. `rₙ ∈ A` （最終状態が受容状態である）

NFAとDFAの関係

NFAとDFAは、共に正規言語を受理する能力を持ちますが、NFAは遷移の非決定性という特徴を持っています。任意のNFAに対して、それと等価な言語を受理するDFAが存在します。NFAをDFAに変換するプロセスは「部分集合構成法」と呼ばれ、NFAの各状態の集合をDFAの一つの状態とみなします。しかし、この変換は最悪の場合、状態数が指数関数的に増加する可能性があります。

NFAの実装方法

NFAを実装するには、主に以下の方法が考えられます。

1. DFAへの変換: NFAを等価なDFAに変換してから実装する方法です。これにより、遷移の扱いが単純化されます。
2. 状態の追跡: NFAが取りうる複数の状態を配列などのデータ構造で追跡し、入力に応じて遷移先を更新します。最終的に受容状態に到達すれば、文字列は受容されます。
3. オブジェクト指向的な実装: NFAオブジェクトを複製し、遷移先ごとに新しいオブジェクトを作成する方法です。再帰関数を用いて同様の実装も可能です。

具体例

例えば、入力文字が0と1であるNFA `M` を考えてみましょう。`M` は、入力文字列に偶数個の0が含まれる場合（最終状態 `S₁`）、または偶数個の1が含まれる場合（最終状態 `S₃`）にその文字列を受理します。

ここで、`M = (S, Σ, T, s₀, A)` であり、

`Σ = {0, 1}`
`S = {S₀, S₁, S₂, S₃, S₄}`
`s₀ = S₀`
`A = {S₁, S₃}`

状態遷移は以下の表で定義されます。


`M`の状態遷移図は以下のようになります。


S0 0> S2
S0 1> S3
S1 0> S0
S1 1> S1
S2 0> S1
S2 1> S2
S3 0> S3
S3 1> S4
S4 0> S4
S4 1> S3


このNFA `M` は、2つのDFAの和集合と考えることができます。1つは状態 `{S₂, S₁}` で、もう1つは状態 `{S₃, S₄}` を持ちます。

最終状態`S₁`にある場合、それまでの入力文字列には偶数個の0が含まれていることを意味します。また、`S₃`にある場合は、それまでの入力文字列に偶数個の1が含まれていることを意味します。NFA `M` が受容する言語は、以下の正規表現で表されます。

`(1(0101)) ∪ (0(1010))`

拡張NFA (GNFA)

拡張非決定性有限オートマトン（GNFA）は、状態遷移が任意の正規表現に対応するNFAです。GNFAは、複数の文字をまとめて読み込み、遷移エッジに付与された正規表現にマッチする文字列を受け付けます。

GNFAの形式的な定義

GNFAは以下の5要素で構成されます。

S: 状態の有限集合
Σ: 入力文字の有限集合
T: 遷移関数 `T: (S - {a}) × (S - {s}) → R`
s: 開始状態 `s ∈ S`
a: 受容状態 `a ∈ S`

ここで、`R` は文字集合 `Σ` から構成される全ての正規表現の集合です。

DFAやNFAはGNFAに簡単に変換でき、GNFAは正規表現に簡単に変換できます。GNFAの各遷移（エッジ）に付与された正規表現を分解し、中間状態を追加することでNFAにも変換できます。したがって、GNFAはDFAおよびNFAと同等の形式言語を理解できます。

もう一度検索