5

DFA では、2 つのオートマトンの状態の外積を計算し、両方の初期オートマトンで受け入れている状態を受け入れることで、2 つのオートマトンの交差を行うことができます。合体も同様に行う。イプシロン遷移を使用してNFAで簡単にユニオンを実行できますが、どのように交差を行うのですか?

4

5 に答える 5

7

DFA と同じように、NFA でクロス積構造を使用できます。唯一の変更点は、ε 遷移の処理方法です。具体的には、クロス積オートマトンの各状態 (q i、r j ) について、その状態から状態の各ペア (q k、r j ) に ε 遷移を追加します。最初のマシンには ε 遷移があります。 q iから q kへ、および 2 番目のマシンで r jから r kへの ε 遷移がある状態 (q i , r k )の各ペアへ。

または、常に NFA を DFA に変換してから、それらの DFA の外積を計算することもできます。

お役に立てれば！

于 2014-02-09T17:32:44.260 に答える
3

ド・モルガンの法則も使用できます: A 交点 B = (A' U B')'

2 つの NFA の賛辞を結合することは、特に結合のイプシロン法に慣れている場合は比較的簡単です。

于 2014-11-04T14:26:43.320 に答える
2

templatetypedef の回答には大きな間違いがあります。

NFA である L1 と L2 のプロダクト オートマトン:

新しい状態 Q = L1 と L2 の状態の積。

今遷移関数：

a は両方のオートマトンのアルファベットを合わせた記号です

デルタ ((q_1、q_2)、a) = delta_L1(q_1、a) X delta_L2(q_2、a)

つまり、delta_L1(q_1 , a) の結果であるセットに、delta_L2(q_1 , a) の結果であるセットを乗算する必要があります。

templatetypedef の回答の問題は、積の結果 (qk ,rk) が言及されていないことです。

于 2015-04-15T04:35:20.420 に答える
1

おそらく遅い答えですが、今日は同様の問題があったので、共有したいと思いました。まず交差点の意味を理解してください。ここで、文字列eが与えられた場合、eは両方のオートマトンで受け入れられるべきであることを意味します。

次のオートマトンを検討してください。

  1. m1言語を受け入れる {w | w には部分文字列として '11' が含まれています}
  2. m2言語を受け入れる {w | w には部分文字列として '00' が含まれています}

直観的に、m = m1 ∩ m2は、部分文字列として '11' と '00' の両方を含む文字列を受け入れるオートマトンです。アイデアは、両方のオートマトンを同時にシミュレートすることです。

ここで、交差点を正式に定義しましょう。

m = (Q, Σ, Δ, q0, F)

  • mの状態を定義することから始めましょう。これは、前述のように、m1とm2の状態のデカルト積です。したがって、m1の状態のラベルとしてa1、a2、およびm2の状態のラベルとしてb1、b2がある場合、Q は次の状態から構成されます: a1b1、a2b1、a1b2、a2b2。この背後にある意味は、 m1とm2の両方でどこにあるかを追跡することです。

  • Σ はおそらく同じままですが、場合によっては異なり、m1とm2のアルファベットの和集合を取ります。

  • q0 は、m1の開始状態とm2の開始状態の両方を含む Q の状態になりました。( a1b1、例を挙げます。)

  • F には状態s IFが含まれ、 sで言及されている両方の状態がそれぞれm1、m2の受け入れ状態であるIF のみが含まれます。

  • 最後になりましたが、重要なことです Δ; 次のように、デカルト積に関してデルタを再度定義します。私は間違っていません。この背後にある直感的なアイデアは、 a1b1をバラバラにして、元のオートマトンで状態a1とb1を検討することです。ここで、考えられる各エッジを「反復」し、たとえば E を選択して、元のオートマトンのどこに到達するかを確認します。その後、デカルト積を使用してこれらの結果を結合します。( a1 , E) がm1に存在し、Δ( b1 , E ) が存在しない場合m2エッジはmに存在しません。それ以外の場合は、何らかの和集合構造になります。

于 2015-11-24T23:35:30.230 に答える
-2

製品オートマトンを構築する代わりに、より複雑な受け入れ基準を許可することができます。通常、NFA は、一連の受け入れ最終状態のいずれかに到達すると、入力文字列を受け入れます。これは、状態のブール値の組み合わせに拡張できます。具体的には、ユニオンの場合と同様に交差点のオートマトンを構築しますが、結果のオートマトンは、両方のオートマトンで最終状態を受け入れる (それに対応する) 場合にのみ入力文字列を受け入れると考えてください。

于 2014-02-13T15:41:01.013 に答える