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

NDFAでは、特定の入力シンボルに対して、マシンはマシン内の状態の任意の組み合わせに移動できます。言い換えれば、機械が移動する正確な状態を判断することはできません。したがって、*非決定的オートマトン*と呼ばれます。状態の数が有限であるため、マシンは*非決定性有限マシン*または*非決定性有限オートマトン*と呼ばれます。

NDFAの正式な定義

NDFAは5タプル（Q、∑、δ、q〜0〜、F）で表すことができます。

Q は有限状態のセットです。
∑ は、アルファベットと呼ばれる有限の記号セットです。
*δ*は遷移関数です。ここで、δ：Q×∑→2 ^ Q ^ +（ここでは、NDFAの場合、状態からQ状態の任意の組み合わせへの遷移が発生する可能性があるため、Q（2 ^ Q ^）のパワーセットが採用されています）
* q〜0〜*は、入力が処理される初期状態です（q〜0〜∈Q）。
F は、Qの最終状態の状態です（F⊆Q）。

NDFAのグラフィカル表現：（DFAと同じ）

NDFAは、状態図と呼ばれる有向グラフによって表されます。

頂点は状態を表します。
入力アルファベットのラベルが付いた弧は、遷移を示します。
初期状態は、空の単一の着信アークによって示されます。
最終状態は二重丸で示されます。

例

非決定的有限オートマトンを→

Q = \ {a、b、c}
∑ = \ {0、1}
q〜0〜= \ {a}
F = \ {c}

以下に示す遷移関数δ-

Present State	Next State for Input 0	Next State for Input 1
a	a, b	b
b	c	a, c
c	b, c	c

そのグラフィカルな表現は次のようになります-

NDFAグラフィカル表現

DFA対NDFA

次の表に、DFAとNDFAの違いを示します。

DFA	NDFA
The transition from a state is to a single particular next state for each input symbol. Hence it is called deterministic.	The transition from a state can be to multiple next states for each input symbol. Hence it is called non-deterministic.
Empty string transitions are not seen in DFA.	NDFA permits empty string transitions.
Backtracking is allowed in DFA	In NDFA, backtracking is not always possible.
Requires more space.	Requires less space.
A string is accepted by a DFA, if it transits to a final state.	A string is accepted by a NDFA, if at least one of all possible transitions ends in a final state.

アクセプター、分類子、およびトランスデューサー

アクセプター（Recognizer）

ブール関数を計算するオートマトンは、*アクセプター*と呼ばれます。アクセプターのすべての状態は、与えられた入力を受け入れるか拒否します。

分類子

*classifier* には3つ以上の最終状態があり、終了時に単一の出力を提供します。

変換器

現在の入力および/または以前の状態に基づいて出力を生成するオートマトンは、*トランスデューサ*と呼ばれます。トランスデューサーは2種類あります-

Mealy Machine -出力は、現在の状態と現在の入力の両方に依存します。
ムーアマシン-出力は現在の状態のみに依存します。

DFAおよびNDFAによる受け入れ可能性

文字列は、DFA/NDFAが初期状態から開始し、文字列を完全に読み取った後に受け入れ状態（最終状態のいずれか）で終わる場合にのみ、DFA/NDFAによって受け入れられます。

文字列Sは、DFA/NDFA（Q、∑、δ、q〜0〜、F）で受け入れられます。

δ（q〜0〜、S）∈F *

DFA/NDFAが受け入れる言語 L は

*\ {S | S∈∑* およびδ*（q〜0〜、S）∈F} *

文字列S 'は、DFA/NDFA（Q、∑、δ、q〜0〜、F）で受け入れられません。

δ（q〜0〜、S ′）∉F *

DFA/NDFAで受け入れられない言語L '（受け入れられた言語Lの補数）は

*\ {S | S∈∑* およびδ*（q〜0〜、S）∉F} *

例

図1.3に示すDFAを考えてみましょう。 DFAから、許容される文字列を導出できます。

DFAによる文字列の許容度

上記のDFAで受け入れられる文字列：\ {0、00、11、010、101、………..}

上記のDFAで受け入れられない文字列：\ {1、011、111、……..}

Automata-theory-non-deterministic-finite-automaton

目次