結合確定性有限自動機

Question

我對這個東西真的很陌生，所以我爲這裏的無所不在而道歉。

構建一個Deterministic Finite Automaton DFA識別下列語言：

L= { w : w has at least two a's and an odd number of b's}. 

的自動執行此(at least 2 a's, odd # of b's)的每一部分都容易使分開......任何人都可以請解釋一個系統的方式將它們組合成一個？謝謝。

Answer 1

它使用兩個自動機的product完成。

Answer 2

語言L其中a至少兩個和b奇怪是一種常規語言。其DFA如下：

在這個DFA中，我在概念上組合了兩個DFS！

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram) 
DFA-2 = for >= two a   (placed Horizontally two times in diagram) 

_{的DFA太症狀和簡單，所以我相信詞，如何既有限自動機}

合併沒有必要作出這樣的DFA你總是跟蹤許多b s已如何被前來要麼偶數或奇數。 States 0, 2 and 4意味着偶數b已經到來。因此，您可以將這個DFA垂直分爲兩部分，其中底部狀態即使是b s，上部狀態也是奇數。

如果奇數b也接受字符串，因此最終狀態應處於上部狀態之一。

不僅b s的數量是條件，但a應該是至少2。因此，您可以將此DFA水平分爲三部分，其中a s的數量爲0,state-0 and 1,a s的數字爲state-2 and 3和a s的數字爲state-4 and 5。在前兩個a之後，任何數量的a都允許在字符串中，因此在狀態爲q4和q5的狀態下有自循環。

_{數目狀態的所需的爲六因爲，2狀態爲奇偶數b和作爲HOULD是ATLEAST 2這樣3種狀態A = 0，A = 1，A = 2，因此2 * 3 = 6}

Answer 3

您可以使用以下簡單步驟構建組合的DFA。

讓Σ = {A 1 ，一個，...，一個_ķ}。
第一步： DFA設計爲兩種語言，並將其命名他們的狀態Q ，Q ...

第2步：重命名這兩個DFA獨特即每一個國家在DFA重命名所有狀態爲Q ，Q ，Q ，Q ，假定你已經開始用標0;這意味着沒有一個國家會有相同的名稱。

第三步驟：通過使用下面的步驟

      3A構建體轉移表（δ）。啓動合併DFA的狀態：
           以啓動二者的DFA（DFA1和DFA2）的狀態，並將其命名爲Q _[I，J]，其中i和j爲開始狀態的下標DFA1和DFA2;即Q _i是第一個DFA的開始狀態，並且Q _j是第二個DFA的開始狀態並且標記Q _[i，j]作爲組合DFA的開始狀態。

      3b。兩者的DFA的地圖狀態
                     如果δ（Q _我，一個_ķ）= Q _P1和δ（Q _Ĵ，一個_ķ ）= Q _p2，其中Q _p1屬於DFA1和Q _p2屬於DFA2然後  δ（Q _[I，J]，一個_ķ）= Q _[P1，P2]

      3C。填寫整個表格，但仍有任何Q _[i，j]保留在轉換表中。

      3d。將合併的DFA的最終狀態：
           對於AND情況下的最終狀態將是所有的Q _[I，J]其中Q _我和Q _Ĵ分別DFA1和DFA2的最終狀態。
           對於OR情況下的最終狀態將是所有的Q _[I，J]其中在q _我或Q _Ĵ是DFA1和DFA2的最終狀態。

第四步： 重命名所有的Q _[I，J]（唯一），並繪製DFA這將是你的結果。

實施例：

L= {w: w has at least two a's and an odd number of b's}. 

第一步：
DFA爲奇數B的的。

DFA至少需要2個a。

第二步：
重命名DFA1
的stae

第三步（A，B，C）：
人工轉換表將作爲。

Step3d：
因爲我們不得不採取兩者DFA所以最終狀態會爲Q _[2,4]，因爲它同時包含DFA的最終狀態。
如果一定要採取OR兩個DFA的最終狀態將爲Q _[0,4]，Q _[2,3]，Q _[1,4]，Q _{[2,1 4]}。
轉換表在添加最終狀態後會喜歡這樣。

步驟4：
重命名所有狀態Q _[I，J]
Q _[0,3]至Q
Q _{[1,2 3]}至Q
Q _[0,4]至Q
Q _[2,3]至Q 4
Q _[1,4]至Q 3
Q _[2,4]至Q
因此，最終的DFA將如下所示。