需要構造DFA（確定性有限自動機）

Question

我需要構造一個DFA，它可以識別所有由0和1完全構成的字符串，以便它有偶數個零和可以被3整除的個數。我發現自動爲偶數0和偶數個1的情況下：

我試圖從這裏去添加一些國家，改變分支機構，等等。不過我仍然不成功通常無法追蹤的有什麼自動機做我會補充的分支和狀態。任何幫助將不勝感激。

Answer 1

你需要用2和3來記錄可分性的狀態，這意味着你需要6個狀態。只要稱它們爲0|0,1|0, 0|1,1|1, 0|2, 1|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或3時讀取的零的數量的模數。然後0|0在這兩種情況下都是模數0，這是接受標準。這一切都有效，因爲要跟蹤的不同狀態的數量是有限的。 DFA這個名稱告訴我們，它無法爲無數的州追蹤。

Answer 2

查看它的一種方法是，問題要求交換2種語言：一種包含偶數個零，另一種包含可被3整除的數目。解決此問題的一種方法是爲兩個語言語言，然後創建另一個DFA，在讀取輸入符號時跟蹤每個DFA中的狀態對。

I have used 'e' and 'o' to denote that the number of zeroes is even or odd respectively. The second digit in each of the states defines the remainder obtained by dividing the number of ones by 3.