你如何構建兩個DFA的聯合？

有沒有人對構造兩個給定DFA的聯合的算法有一個簡單的描述？例如，假設我們有兩個DFA的{0,1}，其中你如何構建兩個DFA的聯合？

{w|w has an odd number of characters} 
    w has states A and B 

delta | 0 | 1 
---------------- 
    A | B | B 
---------------- 
    B | A | A 


{x|x has an even number of 1s} 
    x has states a and b 

delta | 0 | 1 
---------------- 
    a | a | b 
---------------- 
    b | b | a

我表示作爲工會產生的轉換表：

delta | 0 | 1 
---------------- 
    Aa | Ba | Bb 
---------------- 
    Ab | Bb | Ba 
---------------- 
    Ba | Aa | Ab 
---------------- 
    Bb | Ab | Aa

我在講稿有圖案的解決方案，但希望看到別人會如何描述它。從這裏我可以看到，我們基本上是用它們的狀態值「乘」這兩個原始表，以產生一個更大的轉換表。因此可以從結果表中抽取DFA。這聽起來是否正確，是否應該適用於所有DFA案例，還是有我缺少的東西？

來源

2010-12-15 Old McStopher

要理解的關鍵是你必須同時運行這兩個DFA，或者通常你必須在聯合DFA中維護兩個DFA的狀態。

這就是爲什麼您必須爲聯合DFA創建新狀態的原因是直接乘以原始狀態。通過這種方式，您可以在原始DFA中爲每個狀態組合設置一個狀態。

然後可以直接計算新DFA的轉換規則。例如，如果處於狀態Ab，並且輸入爲0，則第一個DFA將轉到狀態B，第二個轉到狀態b，因此聯合DFA的此輸入的下一個狀態將爲Bb。

當您需要製作兩個或更多個DFA的聯合時，此方法適用於所有情況。由此產生的DFA可能不是最優的，但稍後可以使用任何您喜歡的算法將其最小化。

來源

2010-12-15 12:56:50 buc

如果您在某個自動機中發生了不可能的轉換，該怎麼辦？ – 2016-03-06 21:31:09

您將爲不可能轉換的自動機添加E（錯誤）狀態。該自動機將保持該輸入序列的剩餘狀態。我們說這是第一個。然後你會在新的自動機中使用Aa Ab，Ba，Bb，Ea，Eb狀態。 – Nenad 2016-09-23 07:39:35

如果一個自動機只有{0,1}作爲輸入符號，而另一個有{1,2}作爲輸入符號，我認爲它會相似。然後，我們必須用兩個自動機來擴展錯誤狀態（第一個爲E，第二個爲e），如果第二個輸入是第一個將進入E，如果第二個輸入是第二個，則第二個將進入e狀態。 – Nenad 2016-09-23 07:43:29

你如何構建兩個DFA的聯合？

回答

相關問題