0と1だけからなるすべての文字列を認識するDFAを作成する必要があります。そのため、偶数の偶数と3で割り切れる桁数があります。 0の偶数と1の数が偶数の場合のオートマトン:DFA(確定的有限オートマトン)を構築する必要があります
私はなど、いくつかの州を追加枝を変更することで、ここから行くしようとしたが...しかし、私は通常、何のトラックを失う失敗したまま私が追加するブランチと州のbeacuseをオートマトンがやっています。どんな助けでも大歓迎です。
0と1だけからなるすべての文字列を認識するDFAを作成する必要があります。そのため、偶数の偶数と3で割り切れる桁数があります。 0の偶数と1の数が偶数の場合のオートマトン:DFA(確定的有限オートマトン)を構築する必要があります
私はなど、いくつかの州を追加枝を変更することで、ここから行くしようとしたが...しかし、私は通常、何のトラックを失う失敗したまま私が追加するブランチと州のbeacuseをオートマトンがやっています。どんな助けでも大歓迎です。
分裂を2と3で記録する状態が必要です。つまり、6つの状態が必要です。単に0|0
、1|0
、0|1
、1|1
、0|2
、1|2
と呼んでください。最初の桁は、状態に達すると偶数または奇数の零点を持ち、2番目の桁は状態に達すると1の数を持ち、3で割ったときに与えられたモジュラス。
あなたの状態図が含まれています
0|x --0--> 1|x
1|x --0--> 0|x
y|0 --1--> y|1
y|1 --1--> y|2
y|2 --1--> y|0
開始状態はまた、唯一の停止状態である、0|0
です。
重要なビットは、それぞれの状態が、2で割ったときに読み取られるゼロまたは1の数のモジュラスをそれぞれ記録することです。3. 0|0
は、どちらの場合もモジュラス0です。これが受け入れ基準です。これはすべて動作します。追跡するさまざまな状態の数が有限であるためです。 DFAという名前は、無限の数の州を追跡するにはうまくいかないことをすでに教えています。
これを見る一つの方法は、2つの言語の交差点を求めることである:1つは偶数のゼロを含み、もう1つは1で割り切れる数が3である。これに近づく方法は、両方の入力シンボルが読み込まれたときに各DFAの状態のペアを追跡する別のDFAを作成します。
ブリリアント説明、よろしくお願いいたします。最初は面倒な仕事のようなものから本当に簡単な仕事をしました。 ガイドを読んだあと、もう一度図を描きました。[link](http://s10.postimg.org/rzzkzxq6x/DFA.png)。 これが正しいですか? –
よく見えます。状態を2×3グリッドに置くと、対称性が高く、把握がさらに容易になります。 – Harald