我想找出兩個已知的正則表達式之間是否可能存在沖突，以便允許用戶構造一個互斥的正則表達式列表。例如，我們知道下面的正則表達式完全不同，但是它們都匹配xy50：'^xy1\d''[^\d]\d2$'是否可以使用計算機算法確定兩個正則表達式是否存在這種沖突？怎么樣？
3 回答
慕尼黑8549860
TA貢獻1818條經驗 獲得超11個贊
問題可以用“兩個或多個正則表達式描述的語言是否具有非空交集”來重新描述嗎？
如果將問題限制為純正則表達式（沒有反向引用，超前，向后查找或其他允許識別上下文無關或更復雜語言的功能），則該問題至少是可確定的。規則語言在交集下是封閉的，并且有一種算法將這兩個正則表達式作為輸入并在有限時間內生成可識別交集的DFA。
每個正則表達式可以轉換為不確定的有限自動機，然后轉換為確定的有限自動機?？梢詫⒁粚FA轉換為可識別相交的DFA。如果存在從開始狀態到最終DFA的任何接受狀態的路徑，則交集為非空（使用您的術語來說是“沖突”）。
不幸的是，當將初始NFA轉換為DFA時，可能會出現指數爆炸，因此，隨著輸入表達式大小的增加，該問題在實踐中很快變得不可行。
而且，如果允許對純正則表達式進行擴展，那么所有的賭注都將失效-此類語言將不再在交集下關閉，因此該構造將無法正常工作。
- 3 回答
- 0 關注
- 935 瀏覽
添加回答
舉報
0/150
提交
取消