テスト文字列に一致するように、特定の正規表現からDFAを作成しました。発生する場合があり.*ます。（たとえば.*ab）。ここで、マシンが状態1にあるとします。DFAでは、 .*すべての文字のそれ自体への遷移と、状態1から「a」へのaの別の遷移を指します。テスト文字列に「a」が含まれている場合、状態1から、マシンはDFAでは不可能な2つの状態に移行する可能性があるため、遷移となる可能性があります。
質問する
1700 次
2 に答える
5
私はあなたの例から基本的なことから始めます。そうすれば、それが役立つことがわかります。
どのクラスのオートマトンも2つの形式を持つことができます。
- 決定論的
- 非決定論的。
決定論的モデルでは、1つのお祝いから次の構成に移動するための選択肢は1つだけです（または選択肢がないと言います）。有限自動化
（DFA）
の決定性モデルでは、状態（Q）と言語記号（Σ）のすべての可能な組み合わせに対して、常に一意の次の状態があります。
δ(q0, a) → q1
^ only single choice
したがって、DFAでは、ある状態から次の状態へのすべての可能な移動が明確になります。
一方、非決定論的モデル
で
は、次の構成に複数の選択肢があります。
また、有限オートマトン（NFA）の非決定性モデルでは、出力は、状態（Q）と言語記号（Σ）の組み合わせに対する状態のセットです。
NFAの遷移関数の定義：δ：Q×Σ→ 2Q =⊆Q
δ(q0, a) → {q1, q2, q3}
^ is set, Not single state (more than one choice)
NFAでは、次の状態に対して複数の選択肢があります。つまり、移行NFAのあいまいさを呼び出します。
（あなたの例）
言語記号がΣ = {a, b}であり、言語/正規表現がであると仮定します(a + b)*ab。この言語の有限オートマトンは、おそらく次のようになります。
あなたの質問は： 私はそれをより一般的な質問にします。Which state to move when we have more than one choices for next state?
![[autometa]](https://i.stack.imgur.com/guKul.jpg)
NFAで文字列を処理する方法は？
私は、オートマトンの言語に属している場合に文字列を受け入れるアクセプターとしてオートマトンモデルを検討しています（注意：オートマトンをトランスデューサーとして使用できます）、以下は上記の例での私の答えです
上記のNFAには、5つの管状オブジェクトがあります。
1. Σ : {a, b}
2. Q : {q1, ,q2, q3}
3. q1: initial state
4. F : {q3} <---F is set of final state
5. δ : Transition rules in above diagram:
δ(q1, a) → { q1, q2 }
δ(q1, b) → { q1 }
δ(q2, b) → { q3 }
例の有限オートマトンは実際にはNFAです。これは、実動ルールでは、現在の状態が次の状態であるときにシンボルδ(q1, a) → { q1, q2 }を取得した場合、次の状態はまたは（複数の選択肢）のいずれかになる可能性があるためです。したがって、NFAで文字列を処理すると、現在の状態がである間に処理されるシンボルである場所に移動するための追加のパスが得られます。 aq1q1q2aq1
文字列処理の最後にマシンを最終状態にする可能性のある一連の移動がある場合、文字列はNFAによって受け入れられます。そして、初期状態からセット内の最終状態に到達するためのパスを持つすべての文字列のセットはF、NFAの言語と呼ばれます。
「NFAによって定義される言語とは何ですか？」と書くこともできます。なので：
L（nfa）={w⊆Σ*| δ*（q1 、w） ∩F ≠∅}
私が新しいとき、これは私には理解するには複雑すぎましたが、実際にはそうではありませんでした
L（nfa） によると：すべての文字列は言語記号で構成されています=（w⊆Σ*）は言語です。(|)フォームの初期状態（=δ*（q1、w））の処理後に状態 wのセットが最終状態のセットにいくつかの状態を含む場合（したがって、最終状態との交差は空ではありません=δ*（q1、w）∩F ≠∅）。したがって、Σ*で文字列を処理している間、可能なすべてのパスを追跡する必要があります。
例-1abab ：上記のNFSを介して文字列を処理するには：
--►(q1)---a---►(q1)---b---►(q1)---a---►(q1)---b---►(q1)
\ \
a a
\ \
▼ ▼
(q2) (q2)---b---►((q3))
|
b
|
▼
(q3)
|
a
|
halt
上の図は次のとおりababです。NFAで文字列を処理する方法は？
停止：文字列を完全に処理できなかったため、このパスで受け入れられた文字列とは見なされないことを意味します
文字列ababは2つの方向で完全に処理できるため、δ*（q1、w）= {q1、q3}です。
δ*（q1、w）と一連の最終状態の共通部分は{q3}です。
{q1, q3} ∩ F
==> {q1, q3} ∩ {q3}
==> {q3} ≠ ∅
このように、文字列ababaは言語L（nfa）です。
例-2： Σ*からの文字列はabba次のとおりです。処理方法は次のとおりです。
--►(q1)---a---►(q1)---b---►(q1)---b---►(q1)---a---►(q1)
\ \
a a
\ \
▼ ▼
(q2) (q2)
|
b
|
▼
(q3)
|
b
|
halt
到達可能な状態の文字列abbaセットはδ*（q1、w）= {q1、q2}であり、このセットの最終状態はありません。これは、=> Fとの交差が∅空のセットであるため、文字列abbaは受け入れられない文字列であることを意味します。 （言語ではありません）。
これは、非決定性有限オートマトンで文字列を処理する方法です。
いくつかの追加の重要な注意事項：
有限オートマトンの場合、決定論的モデルと非決定論的モデルの両方が同等に機能します。非決定論的モデルには、言語を定義するための追加機能はありません。したがって、NFAとDFAの範囲は、正規言語と同じです。（これは、PDAのスコープなどの自動化のすべてのクラスに当てはまるわけではありません！= NPDA）
非決定論的モデルは、理論的な目的、比較的エッセイを描くのに役立ちます。一方、実装の目的では、常に決定論的モデル（効率のために最小化）が必要です。そして幸いなことに、有限オートメタのクラスでは、すべての非決定論的モデルを同等の決定論的モデルに変換できます。NFAをDFAに変換するアルゴリズム手法があります。
DFAの単一の状態で表される情報は、NFA状態の組み合わせで表すことができるため、NFAの状態の数は同等のDFAよりも少なくなります。（証明は利用可能ですnumberOfStates（DFA）<= 2 power numberOfStates（NFA）すべてのセットの組み合わせがpowersetであるため）
上記の正規言語のDFAは次のとおりです。
このDFAを使用すると、Σ*内の任意の文字列の初期状態から最終状態への一意のパスが常に見つかり、セットの代わりに単一の到達可能な最終状態に到達し、その状態が最終のセットに属する場合、その入力文字列は次のようになります。文字列（言語）を受け入れるか、そうでない場合は/
（あなたの表現は、通常、理論科学.*abでは同じですが、連結以外のドット演算子(a + b)*abは使用しません.）
于 2013-03-27T14:23:11.113 に答える
0
このような正規表現との一致は、バックトラックを介して行われます。次の状態についてあいまいな場合、評価は最初の選択を行い、それが選択したことを記憶します。最初の選択肢を選択した結果、一致しなかった場合、評価は最後の選択肢に戻り、その状態から次に利用可能な選択肢を試します。
そのようなメカニズムが厳密なDFAに対応しているかどうかはわかりません。
于 2013-03-25T14:53:54.477 に答える