有沒有辦法檢查兩個正則表達式是否可以匹配相同的字符串？

Question

我有兩個正則表達式。我需要確定是否可以同時創建與這兩個正則表達式匹配的給定長度的字符串。我需要算法來做到這一點。

字符串的長度不會超過20個字符。

Answer 1

這取決於。對於perl兼容的正則表達式（pcre），這通常是不可能的，因爲它們是完整的：你甚至不能確定匹配總是終止。

對於Chomsky層次結構中定義的「乾淨」形式的調節語言，已知它們在交叉點處關閉，這已在this thread中討論過。

只要您有交集的NFA，就很容易檢查是否有任何字符串匹配它 - 如果thera是從NFA的開始到結束的路徑，那麼此路徑的字符串是字符串你正在尋找，對於DFA，給出了一個算法here，它適應NFA應該很簡單。