如何檢測兩個正則表達式在可匹配的字符串中是否重疊？

Question

我有一個正則表達式的容器。我想分析它們以確定是否可以生成一個匹配多於一個的字符串。考慮到這個用例，我寫了自己的正則表達式引擎，在C++或Python中有沒有簡單的方法來解決這個問題？

Answer 1

有沒有簡單的方法。

只要你的正則表達式只使用標準功能（Perl讓你嵌入任意代碼進行匹配，我認爲），你可以從每一個產生一個nondeterministic finite-state automaton (NFA)，緊湊地編碼RE匹配的所有字符串。

鑑於任何一對NFA，它們的交集是否爲空是可判定的。如果交叉點不是空的，則一些字符串匹配對中的兩個RE（相反）。

標準的可判定性證明首先確定它們爲DFA，然後構造一個新的DFA，其狀態是兩個DFA狀態的對，其最終狀態恰好是這兩個狀態都是最終狀態的最終狀態在他們的原始DFA中。或者，如果您已經展示瞭如何計算NFA的補數，那麼您可以（DeMorgan的定律）通過complement(union(complement(A),complement(B)))得到交點。不幸的是，NFA-> DFA涉及潛在的指數大小爆炸（因爲DFA中的狀態是NFA中的狀態子集）。從Wikipedia：

正規語言的一些類可以 只能由確定性 有限自動機，其大小在 最短相當於普通 表達式的大小增長 成倍描述。標準示例是 ，其中語言L_k由 組成，所有字符串在字母{a，b} 的第k個最後一個字母等於a。

順便說一下，你應該使用OpenFST。您可以創建自動文本作爲文本文件，並玩弄最小化，交叉等操作，以查看它們對於您的問題有多高效。已經有開源的regexp-> nfa-> dfa編譯器（我記得有一個Perl模塊）;修改一個輸出OpenFST自動機文件並播放。

幸運的是，有可能避免子集的態爆炸和相交2 NFA直接使用相同的建設作爲DFA：

如果A ->a B（在一個NFA，你可以去從狀態A到B在交叉

(C,Z)輸出字母 'a'）

和X ->a Y（在其他NFA）

(A,X) ->a (B,Y)然後是最後當且僅當C ^在一個NFA中是最後的，而Z在另一箇中是最後的。

要關閉此過程，請從兩個NFA的啓動狀態開始，例如， (A,X) - 這是交叉點NFA的開始狀態。每次你第一次訪問一個狀態時，通過上述規則爲離開這兩個狀態的每一對弧產生一個弧，然後訪問這些弧到達的所有（新）狀態。您將存儲事實，即您擴展了狀態的弧（例如，在一個散列表中），並最終探索從一開始就可以訪問的所有狀態。

如果允許小量的轉變（即不輸出字母），這很好：

如果在第一NFA A ->epsilon B，那麼對於每一個國家(A,Y)到達，加上弧形(A,Y) ->epsilon (B,Y)，同樣在epsilons第二名NFA。

在將正則表達式轉換爲NFA時，Epsilon轉換對於獲得兩個NFA的聯合是有用的（但不是必需的）;每當你有變化regexp1|regexp2|regexp3，你採取聯盟：一個NFA的開始狀態有一個epsilon過渡到代表交替的正則表達式的每個NFA。確定NFA的空白很容易：如果您從開始狀態進行深度優先搜索時達到最終狀態，則它不是空的。

這個NFA交點類似於有限狀態轉換器組合（換能器是NFA，輸出符號對，成對連接以匹配輸入和輸出串，或將給定輸入轉換爲輸出） 。

Answer 2

從理論上講，你所描述的問題是不可能的。在實踐中，如果您擁有使用有限子集或正則表達式語法的可管理數量的正則表達式和/或可用於匹配正則表達式容器的有限字符串選擇，那麼您可能會能夠解決它。

假設您不是試圖解決抽象的一般情況，可能有些事情可以解決實際應用。也許如果你提供了一個有代表性的正則表達式樣本，並描述了你將要匹配的字符串，可以創建一個啓發式來解決這個問題。

Answer 3

This regex inverter（使用pyparsing編寫）適用於re語法的有限子集（例如，不允許*或+） - 您可以將兩個re倒置爲兩個集合，然後查找集合交集。