以下の言語のためのDFAを構築：少なくとも3個の0と最大で2 1Sを持っているすべての文字列

Question

私は2つのシンプルなのDFAの交差点からDFAを構築することです。最初のシンプルなDFAは、少なくとも3個の0を持っているすべての文字列の言語を認識し、第二シンプルな言語DFAは、最大2つの1の文字列の言語を認識します。アルファベットは、（0,1）です。私は2つを組み合わせて、より大きなDFAを構築するかどうかはわかりません。ありがとう！

Answer 1

ここでは一般的な考え方だ。

は、これを行うための最も簡単な方法は、彼らがお互いに「平行」であるように、あなたが見てきた1の数に基づいており、あなたの0をカウントするための異なるパスを持つことです。あなたは割り当ての正確な性質に応じて、第三1を参照してください場合は、これを凝縮することができるかもしれない次のパスの一つの層からあなたが1を参照してくださいすべての時間を移動し、トラップ状態に最後の層から移動あなたが基本的なレイアウトを持っていたら、あなたはそれを判断することができます。通常、あなたが小さい最終的な結果を生成するために、第2のDFAにおける状態で最初にDFAから状態を組み合わせることができます。

ここではより多くの数学的な説明のです。

  

ののためのオートマトンを構築   交差点操作。の
  私たちがしていると仮定   2 DFA M1 =（S1、Q（1）0、T1、所与   F1）とM2 =（S2、Q（2）0、T2、F2）。   これら二つのDFAは、言語を認識し、L1 =   L（M1）及びL2 = L（M2）。私たちがしたいです   設計DFA M =（S、Q0、T、F）は   交差点L1∩L2を認識しています。我々   DFAを構築する考えを使用   言語の労働組合のために。 ANを考えます   我々はワットにM1とM2を実行し、wを入力   同時に、我々はのために説明したように   組合操作。我々が完了したら、   W上のM1のとM2のランは、私たちが見て   これら二つの結果の終了状態   実行されます。両端状態が受諾された場合   その後、私たちは、そうでない場合、我々は拒否し、wを受け入れます   ワット

<時間> 新しい遷移関数を構築する場合、

は、それを考えるための簡単な方法は、状態のペアを使用することです。たとえば、次のDFAを考慮します：

さて、私たちは、同時に両方のDFAを横断することによって、これらを組み合わせて開始することができます。我々は、入力としてaを参照してくださいたとえば、状態1で両方のスタートは今、何が起こりますか？まあ、DFA1 1-> 2から行くだろう、とDFA2 1-> 3から移動します。組み合わせる場合、その後、我々は交差点が状態から行くだろうと言うことができる「1,1」状態「2,3」に（両方のDFAが状態1です）。状態2の DFA1の状態を受け入れ、状態が「2,3」は私たちの新しいDFA3状態を受け入れているように、の状態3はDFA2で受け入れる状態は、あるあります。我々は、すべての州/トランジションのためにこれを繰り返し、で終わることができます：

はその理にかなっていますか？

参考：画像はでから、この割り当てを見つけコーネル大学ます。

Answer 2

最も簡単な方法は、 2DFA のモデルを使用することになりますから、エンド第DFAの状態（少なくとも3ゼロのための1つの試験）第1の開始状態へのジャンプ、及び入力の先頭に逆。そして、第二DFAは、文字列をテストしてみましょう。