NFA如何實現否定正則表達式

我知道，NFA可以很容易地結合正則表達式像aba|b和a*

和各種[ab]可以轉換爲a|b

，但我怎麼能轉換[^ab]爲NFA片段？

2013-02-04 Zava

這只是一個角色類。 NFA的轉換標記有單個字符或lambda（空字符串）。要實現一個字符類，只需要爲該類中的每個字符進行轉換。否定班級只是在班級中爲每個字符而不是實施一次過渡。由於NFA需要使用有限的字母表，因此這完全沒有問題。如果A是字母表並且您想要[^ ab]，那麼您需要對集合A - {a，b}中的每個字符進行一次轉換。

來源

2013-02-04 03:58:54 Gene

這是一個好主意，但這意味着當NFA收到一個字符時，它會對每個狀態的轉移進行foreach。實際上，我使用像multiMap這樣的數據結構來實現一個傳輸，它將通過字符散列來查找下一個狀態，並且在大多數情況下，它比狀態中的foreach傳輸更快。 – Zava

謝謝，我用混合風格實現了它。 – Zava

生產掃描儀通常將字符類編碼爲狀態編號數組，每個字符一個元素，或者如果類簡單，則將編碼的間隔列表排序。但是生產掃描儀不使用NFA，因爲它們比DFA慢得多。 – Gene

NFA如何實現否定正則表達式

回答

相關問題