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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/20 14:47 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "非決定性有限オートマトン" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2023年9月）

非決定性有限オートマトン^[1]（ひけっていせいゆうげん-（）、英: Nondeterministic Finite Automaton）または非決定性有限状態機械^[2]（ひけっていせいゆうげんじょうたいきかい（）、英: Nondeterministic Finite State Machine）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。

直感的説明

NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。

${\displaystyle S_{1}{\overset {c_{1}}{\longrightarrow }}S_{2}{\overset {c_{2}}{\longrightarrow }}\cdots {\overset {c_{n-1}}{\longrightarrow }}S_{n}}$

M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S₂, S₁} を持ち、もうひとつは状態 {S₃, S₄} を持つ。

最終状態 S1 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 S2 にあるときは奇数個であることを意味する。1 が入力されたとき、上のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 0 が含まれていた事がわかる。

最終状態 S3 にあるとき、それまでの入力文字列に偶数個の 1 が含まれていたことを意味し、状態 S4 にあるときは奇数個であることを意味する。0 が入力されたとき、下のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 1 が含まれていた事がわかる。

Mの言語は以下の正規表現で記述される正規言語である。

${\displaystyle (1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})}$

拡張NFA（GNFA）

拡張非決定性有限オートマトン（GNFA^[5]）または拡張非決定性有限状態機械^[6]とは、各状態遷移が任意の正規表現に対応する NFA である。GNFA は入力からまとめて複数の文字を読み込むが、その文字列は遷移（エッジ）に付記された正規表現に対応するものである。

形式的定義

GNFA は、${\displaystyle (S,\Sigma ,T,s,a)}$ の5要素から構成され、各要素は以下の性質を持つ。

• 状態の有限集合（${\displaystyle S}$）
• 入力文字の有限集合（Σ）
• 遷移関数（${\displaystyle T:(S-\{a\})\times (S-\{s\})\rightarrow R}$）
• 開始状態（${\displaystyle s\in S}$）
• 受容状態（${\displaystyle a\in S}$）

ここで ${\displaystyle R}$ は文字集合 ${\displaystyle \Sigma }$ から構成される全ての正規表現の集合である。

DFA や NFAは簡単に GNFA に変換でき、GNFA は正規表現に簡単に変換できる。その変換は、中間的な遷移を正規表現に変換していき、最終的に ${\displaystyle S=\{s,a\}}$ というひとつの遷移（エッジ）になるようにするものである。同様に GNFA の各遷移（エッジ）に付記された正規表現を一文字ずつに分解するまで中間状態を追加していけば NFA に変換できる。さらに NFA は前述したように DFA に変換可能である。したがって GNFA は DFA および NFA と等価な形式言語を理解する。

脚注

1. ^ 英: non-deterministic finite automaton
2. ^ 英: non-deterministic finite state machine
3. ^ “Finite State Machine”. FOLDOC. NFA ==> Finite State Machine. 2010年6月16日06:52:21時点のオリジナルよりアーカイブ。2005年11月20日 06:00閲覧。
4. ^ A. V. エイホ・R. セシィ、J. D. ウルマン 著、原田 賢一 訳『コンパイラI: 原理・技法・ツール』 1巻、サイエンス社、2000年、139頁。ISBN 4-7819-0585-4。 
5. ^ 英: generalized non-deterministic finite automaton
6. ^ 英: generalized non-deterministic finite state machine