首頁猿問正則表達(dá)式：確定兩個(gè)正則表達(dá)式是否...

正則表達(dá)式：確定兩個(gè)正則表達(dá)式是否可以匹配相同的輸入？

正則表達(dá)式

揚(yáng)帆大魚 2019-12-27 09:57:46

我想找出兩個(gè)已知的正則表達(dá)式之間是否可能存在沖突，以便允許用戶構(gòu)造一個(gè)互斥的正則表達(dá)式列表。例如，我們知道下面的正則表達(dá)式完全不同，但是它們都匹配xy50：'^xy1\d''[^\d]\d2$'是否可以使用計(jì)算機(jī)算法確定兩個(gè)正則表達(dá)式是否存在這種沖突？怎么樣？

查看完整描述

3 回答

慕尼黑8549860

TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超11個(gè)贊

問題可以用“兩個(gè)或多個(gè)正則表達(dá)式描述的語言是否具有非空交集”來重新描述嗎？

如果將問題限制為純正則表達(dá)式（沒有反向引用，超前，向后查找或其他允許識(shí)別上下文無關(guān)或更復(fù)雜語言的功能），則該問題至少是可確定的。規(guī)則語言在交集下是封閉的，并且有一種算法將這兩個(gè)正則表達(dá)式作為輸入并在有限時(shí)間內(nèi)生成可識(shí)別交集的DFA。

每個(gè)正則表達(dá)式可以轉(zhuǎn)換為不確定的有限自動(dòng)機(jī)，然后轉(zhuǎn)換為確定的有限自動(dòng)機(jī)?？梢詫⒁粚FA轉(zhuǎn)換為可識(shí)別相交的DFA。如果存在從開始狀態(tài)到最終DFA的任何接受狀態(tài)的路徑，則交集為非空（使用您的術(shù)語來說是“沖突”）。

不幸的是，當(dāng)將初始NFA轉(zhuǎn)換為DFA時(shí)，可能會(huì)出現(xiàn)指數(shù)爆炸，因此，隨著輸入表達(dá)式大小的增加，該問題在實(shí)踐中很快變得不可行。

而且，如果允許對純正則表達(dá)式進(jìn)行擴(kuò)展，那么所有的賭注都將失效-此類語言將不再在交集下關(guān)閉，因此該構(gòu)造將無法正常工作。

反對回復(fù) 2019-12-27