正則表達式相等

Question

有沒有辦法找出兩個任意正則表達式是否相等？對我來說看起來很複雜，但是可能有一些DFA簡化機制或者其他什麼？

Answer 1

要測試等價你可以計算minimal DFAs的表情和對它們進行比較。

Answer 2

這兩個Perlmonks線程討論這個問題（特別是讀blokhead的反應）：

• Comparative satisfiability of regexps
• Testing regex equivalence

Answer 3

等式的可測性是正則表達式的經典屬性之一。 （注：這如果你真的在談論Perl的正則表達式或一些其他技術上非正規 superlanguage不成立。）

把你的資源來推廣有限自動機A和B，然後建立一個新的自動機AB這樣A的接受狀態具有空轉變到B的開始狀態，並且B的接受狀態被反轉。這給你一個自動機，接受A接受的所有字符串，除了所有被B接受的字符串外。

對B-A做同樣的事情，並且同時減少到純粹的FA。如果FA沒有從起始狀態可訪問的接受狀態，則接受空語言。如果你能證明這兩個AB和BA都是空的，你已經表明，A = B.

Edit嘿，我不能相信沒有人注意到巨大的錯誤 - 故意之一，當然： - p

如上所述的自動機AB將接受那些其前半部分被A接受並且後半部分不被B接受的字符串。構建期望的 AB是稍微複雜的過程。我不能把它想成我的頭頂，但我確實知道它是明確的（並且可能涉及創建狀態來表示接受A的狀態和B中的非接受狀態的產物）。

Answer 4

這真的取決於你的意思是正則表達式。正如其他海報所指出的那樣，將這兩種表達方式都縮減爲最小DFA應該可行，但它僅適用於純正則表達式。

真實世界中使用的一些結構正則表達式庫（特別是反向引用）使它們有能力表達不規則的語言，所以DFA算法不適用於它們。例如，正則表達式：([a-z]*) \1匹配由空格（a a和b b但不是b a或a b）分隔的相同單詞的雙重出現。這完全不能被有限自動機識別。