正則表達式比較

Question

是否有任何解決方案可以比較兩個正則表達式的包含，部分重疊，不相交，即我想知道如何比較兩個正則表達式。其次，如果正則表達式1被正則表達式2拋出，我可以組合兩個正則表達式。

Answer 1

假設您有兩個表達式A和B，並且想知道A是否匹配B的子集。

您需要計算B的最小化DFA，然後組合這兩個表達式以形成A和B的聯合，然後計算該新表達式的最小化DFA。如果這兩個DFA相等，那麼A匹配B的一個子集。

實質上，如果不經過構造最小化自動機的過程，就無法正確地檢查它。然而，它會給這個問題提供可驗證的真實答案。

結合這兩個表達式可以通過創建一個新的表達式，如(A)|(B)來完成，如果引擎支持這個表達式，可能會將paranthesis替換爲非捕獲類型。

如果你決定去整個方式做算法，我已經寫了一系列的文章的過程：

http://binarysculpting.com/2012/02/11/regular-expressions-how-do-they-really-work-automata-theory-for-programmers-part-1/

http://binarysculpting.com/2012/02/15/converting-dfa-to-nfa-by-subset-construction-regular-expressions-part-2/

http://binarysculpting.com/2012/03/21/dfa-state-minimization/

比較兩個自動機可以檢查狀態和轉換是否相同。他們應該完全平等。