互斥正則表達式

Question

如果我有一個正則表達式列表，是否有一種簡單的方法可以確定它們中的任何一個都不會返回匹配的字符串？

也就是說，當且僅當對於所有字符串，列表中最多一個項目將匹配整個字符串時，該列表纔有效。

這似乎很難（也許是不可能的？）來明確地證明，但我似乎無法找到關於這個問題的任何工作。

我問的原因是我正在接受正則表達式的標記器，我想確保一次只有一個標記可以匹配輸入頭。

Answer 1

如果您使用純正則表達式（沒有反向引用或其他功能導致它們識別上下文無關或更復雜的語言），那麼您可能會問什麼。 您可以做的是將每個正則表達式轉換爲DFA，然後（由於常規語言在相交處關閉）將它們組合到DFA中，以識別這兩種語言的交集。如果該DFA具有從開始狀態到接受狀態的路徑，則該輸入正則表達式會接受該字符串。

這個問題是，通常的正則表達式 - > DFA算法的第一步是 將正則表達式轉換爲NFA，然後將NFA轉換爲DFA。但是最後一步 會導致DFA狀態數量出現指數式放大，所以對於非常簡單的正則表達式，這隻能是 。

如果您使用的是擴展正則表達式語法，則所有投注均爲關閉：上下文無關語言 在交集之下未關閉，因此此方法不起作用。

Answer 2

的Wkipedia article on regular expressions確實狀態

是可能的寫的算法對於兩個給定正則表達式決定所描述的語言是否基本相等，減小了每個表達式的最小確定性有限狀態機，並判斷它們是否是同構的（等價的）。

但沒有提供進一步的提示。

當然，以後的簡單方法是進行大量測試 - 但我們都知道測試作爲一種證明方法的缺點。

Answer 3

你不能這樣做只看正則表達式。

考慮你有[0-9]和[0-9]+的情況。它們顯然是不同的表達式，但是當應用到字符串「1」時，它們都會產生相同的結果。當應用於字符串「11」時，它們產生不同的結果。

重點是正則表達式不夠信息。結果取決於正則表達式和目標字符串。