將RE轉換爲NFA

Question

哪一個是顯示RE union 0 + 1的正確方法？我看到了這兩種方式，但我認爲兩種方式都是正確的。如果兩者都是正確的，爲什麼複雜的事情？

Answer 1

他們都是正確的，因爲你說。

第一個看起來像是使用一套標準規則生成的 - 在這種情況下，它是過度殺傷（而且看起來很傻），但在更復雜的情況下，遵循簡單的規則比保存整個事物更容易在你的腦海中，從頭開始編寫相應的NFA。一般來說，NFA可以被重寫，使其具有單一的最終狀態（顯然已經只有一個起始狀態）。

然後，可以將這種形式的兩個NFA組合起來，使得它們組合時所接受的語言是它們單獨接受的語言的聯合 - 這對應於正則表達式中的或（+）。爲了以這種方式組合NFA，只需創建一個新節點作爲起始狀態，並將它與ε轉換連接到兩個NFA的開始狀態。我們創建了一個額外的節點來作爲統一的最終狀態，並且爲了使NFA在單個最終狀態下完整地結束（這樣我們可以使用這個NFA遞歸地用於其他工會，如果我們想要的話）將舊的最終狀態（即失去其最終狀態）連接到它。

使用上面的一般規則，很容易得出第一個圖（兩個NFA聯合在一起，第一個匹配的0，另一個1） - 第二個很容易通過常識到達，因爲它非常簡單正則表達式;-)

Answer 2

第一個構造屬於帶有電子移動的NFA類，它是一般NFA類的擴展。電子移動讓您無需輸入即可進行轉換。對於轉換函數，僅使用電子轉換來計算從給定狀態可達到的狀態集非常重要。顯然，添加電子移動不允許NFA接受非正規語言，因此它最終等同於NFA和DFA。

Thompson的構造算法使用NFA與電子移動從任何正則表達式構建自動機。它提供了一個標準的方法來構建一個自動機從正則表達式時，它可以方便地自動化施工。