我知道如何在語言上應用 Kleene 星,但我不確定如何將它應用到 DFA 或 NFA。我很確定它需要是 epsilon NFA,初始狀態是最終狀態,最終狀態可能需要 epsilon 轉換到該初始狀態?
有什么演算法可以解決這個問題嗎?這個接受以 Kleene 星開頭0和結尾的單詞的 DFA 將如何1應用于它?
uj5u.com熱心網友回復:
在我看到的正則運算式和有限自動機等價的至少一個證明中,給出了一個結構來顯示如何將具有與正則運算式 s 的語言對應的語言的 NFA 轉換為具有與該語言對應的語言的 NFA運算式 s*。我認為結構是這樣的:
- 也接受的新初始狀態 q0'
- 從 q0' 到前一個初始狀態 q0 的 lambda/epsilon/empty 轉換
- lambda/epsilon/empty 從每個接受狀態(除了 q0')轉換回 q0'
這允許:
- 要接受的空字串,即使之前不是
- 要接受的原始 NFA 語言的任何字串連接
轉載請註明出處,本文鏈接:https://www.uj5u.com/yidong/471197.html
