如何合併兩個有限狀態自動機？

說我有由下面的轉移圖表示的兩個確定性有限狀態自動機：如何合併兩個有限狀態自動機？

FSA關鍵字IF： IF

___  ___   _ 
/ \ I / \ F // \\ 
>| 0 |----->| 1 |----->||2|| 
\___/  \___/  \\_//

FSA用於ID： [AZ] [A-Z0 -9] *

  ------------ 
    ___  | _ LET | 
/ \ LET // \\<------ 
>| 0 |----->||1|| 
\___/  \\_//<------ 
      |  NUM | 
      ------------

我可以用什麼算法來他們有三個最終狀態合併成一個單一的確定性有限狀態自動機，代表由下面的轉移圖不滿：

  ----------------------- 
      | LETTER BUT F OR NUM | -------- 
    ___  | _   _ LET v _ | LET | 
/ \ I // \\ F // \\----->// \\<------ 
>| 0 |----->||1||----->||2||  ||3||<-------- 
\___/  \\_//  \\_//----->\\_//<------ | 
    |       NUM |  NUM | | 
    | ANY LETTER OTHER THAN I  ------------ | 
    --------------------------------------------- 

1: ID 
2: IF (IT'S ALSO AN ID, BUT THE KEYWORD IF HAS A HIGHER PRECEDENCE) 
3: ID

來源

2012-06-26 Aadit M Shah

狀態2和3之間的'NUM'轉換來自組合機器的哪個部分？否則，它看起來像要連接機器並從狀態0添加故障轉換。 –

忘記添加這些匆忙。 –

您是否手動繪製了這些ascii藝術作品或者您使用過工具？非常整潔的方式。 – Loax

教科書通常通過在其上施加de-morgan，L（C）=（L（A）給出了自動機C使得L(C) = L(A) U L(B)^Ç [相交] L（B） ^C）^C。
該交點是通過構建笛卡爾積自動機來完成的，否定就是簡單地切換接受狀態。
建立工會的自動機也可以直接完成：建立笛卡爾乘積自動機，和最終狀態是(a,b)這樣a是在A或b自動機的最終狀態可以在B

自動機的最終狀態

另一種方法是通過簡單地創建一個新狀態併爲start（A）和start（B）添加一個epsilon路徑，並使用標準算法消除自動機中的非確定性，從而構建一個Non-Deterministic Final Automaton（NFA）。

問題 - 這個自動機不會很小（很可能）。您可以嘗試在結果自動機上使用this algorithm以最小化它。

來源

2012-06-26 06:44:12 amit

創建非確定性有限狀態自動機並將其轉換爲確定性有限狀態自動機是一個簡單的解決方案。謝謝。我也會學習德摩根的法則。 =） –

如何合併兩個有限狀態自動機？

回答

相關問題