Automata-theory-non-deterministic-finite-automaton
非決定性有限オートマトン
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 |
そのグラフィカルな表現は次のようになります-
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)
ブール関数を計算するオートマトンは、*アクセプター*と呼ばれます。 アクセプターのすべての状態は、与えられた入力を受け入れるか拒否します。
分類子
変換器
現在の入力および/または以前の状態に基づいて出力を生成するオートマトンは、*トランスデューサ*と呼ばれます。 トランスデューサーは2種類あります-
- Mealy Machine -出力は、現在の状態と現在の入力の両方に依存します。
- ムーアマシン-出力は現在の状態のみに依存します。
DFAおよびNDFAによる受け入れ可能性
文字列は、DFA/NDFAが初期状態から開始し、文字列を完全に読み取った後に受け入れ状態(最終状態のいずれか)で終わる場合にのみ、DFA/NDFAによって受け入れられます。
文字列Sは、DFA/NDFA(Q、∑、δ、q〜0〜、F)で受け入れられます。
δ(q〜0〜、S)∈F *
DFA/NDFAが受け入れる言語 L は
文字列S 'は、DFA/NDFA(Q、∑、δ、q〜0〜、F)で受け入れられません。
δ(q〜0〜、S ′)∉F *
DFA/NDFAで受け入れられない言語L '(受け入れられた言語Lの補数)は
例
図1.3に示すDFAを考えてみましょう。 DFAから、許容される文字列を導出できます。
上記のDFAで受け入れられる文字列:\ {0、00、11、010、101、………..}
上記のDFAで受け入れられない文字列:\ {1、011、111、……..}