我如何找到D FA的關閉

Question

我正在嘗試實施D FA的關閉。我沒有使用N FA，我成功實施了聯盟，恭維交叉口，DFA的減法和級聯。我們的老師沒有告訴我們找到閉包的算法。我試圖通過將D FA連接到它自己來做到這一點，但很顯然它沒有奏效。

我只需要通過使用矩陣代表D FA的方式。除了可以請您詳細說明Klein關閉之外，我相信一旦我知道如何結束關閉，我就可以做到這一點。

Answer 1

我不確定一般情況下關閉的意思。但是對於Kleene閉包，您可以這樣進行：從每個最終狀態開始，您都會添加一個epsilon轉換（不會讀取任何內容）到開始狀態。因此，在閱讀完該語言的一個詞後，可以從另一個詞開始。

當然，得到的自動機不再是確定性的。但有一些標準程序可以再次確定它。

對於直接構造：查看所有進入最終狀態的轉換，例如（q，a） - > f。從傳出狀態添加另一個讀取相同符號並轉到起始狀態的轉換：（q，a） - > s。所以自動機有可能完成閱讀單詞，然後再次開始。