正則表達式「包含」另一個正則表達式

Question

有沒有方法可以測試正則表達式是否包含另一個正則表達式？
例如：

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b"; 

regex1的 「包含」 RegEX2。

據我所知 - 這是做不到的，我錯了嗎？

---

好的，joel.neely已經表明它可以在學術上完成（還沒有讀過......）。

可以用C＃編程語言來完成嗎？
那會有多有效？測試1000對需要多長時間？

Answer 1

是的。

This paper包含有關該主題的詳細討論（請參閱第4.4節）。

Answer 2

將兩個表達式轉換爲等價的狀態機，並檢查兩臺機器中的所有路徑是否允許相同的匹配，應該有所斬斷。抽水馬克應該很明顯，所以避免重新訪問舊節點。

它只適用於「簡單」正則表達式（或真實的，你有什麼，perls遞歸表達式更富有表現力）。

雖然狀態機的圖形可能有大量的路徑，但它仍應該受到限制（尤其是表達式的來源是人爲的）。因此，您可以找到RegEX1的所有允許路徑，然後逐個檢查RegEX2中是否允許。如果所有路徑都是有效的，你就會知道那個路徑包含在另一個路徑中。