2つの単純なDFAの共通部分からDFAを構築します。最初の単純なDFAは、少なくとも3つの0を持つすべての文字列の言語を認識し、2番目の単純な言語DFAは、最大2つの1の文字列の言語を認識します。アルファベットは（0,1）です。2つを組み合わせてより大きなDFAを構築する方法がわかりません。ありがとう！
13321 次
2 に答える
7
一般的な考え方は次のとおりです。
これを行う最も簡単な方法は、見た1の数に基づいて、0をカウントするためのさまざまなパスを用意し、それらが互いに「平行」になるようにすることです。1が表示されたらいつでもパスのあるレイヤーから次のレイヤーに移動し、3番目の1が表示されたら最後のレイヤーからトラップ状態に移動します。割り当ての正確な性質によっては、これを凝縮できる場合があります。 、しかし、基本的なレイアウトができたら、それを決定できます。通常、最初のDFAの状態と2番目のDFAの状態を組み合わせて、より小さな最終結果を生成できます。
これがより数学的な説明です：
交差操作のオートマタを構築します。
2つのDFAM1=（S1、q（1）0、T1、F1）およびM2 =（S2、q（2）0、T2、F2）が与えられていると仮定します。これらの2つのDFAは、言語L1 = L（M1）およびL2 = L（M2）を認識します。交差点L1∩L2を認識するDFAM=（S、q0、T、F）を設計します。言語の結合のためにDFAを構築するというアイデアを使用します。入力wが与えられると、ユニオン操作について説明したように、wでM1とM2を同時に実行します。wでM1とM2の実行を終了したら、これら2つの実行の結果の終了状態を確認します。両方の終了状態が受け入れている場合はwを受け入れ、そうでない場合はwを拒否します。
新しい遷移関数を作成するとき、それを考える簡単な方法は、状態のペアを使用することです。たとえば、次のDFAについて考えてみます。
これで、両方のDFAを同時にトラバースすることで、これらの組み合わせを開始できます。たとえば、どちらも状態1から始まります。a入力として表示するとどうなりますか？さて、DFA1は1-> 2になり、DFA2は1->3になります。組み合わせると、交差点は状態「1,1」（両方のDFAは状態1）から状態「2,3」になると言えます。状態2はDFA1の受け入れ状態であり、状態3はDFA2の受け入れ状態であるため、状態「2,3」は新しいDFA3の受け入れ状態です。すべての状態/遷移に対してこれを繰り返すことができ、最終的には次のようになります。
それは理にかなっていますか？
参照：コーネル大学からのこの課題で見つかった画像。
于 2010-10-26T14:40:55.790 に答える
0
最も簡単な方法は、2DFAモデルを使用することです。最初のDFAの終了状態（少なくとも3つのゼロをテストするもの）から2番目のDFAの開始状態にジャンプし、入力の開始に逆戻りします。次に、2番目のDFAで文字列をテストします。
于 2010-10-26T15:06:00.243 に答える