確定一個正則表達式是否是另一個

我收集了大量的正則表達式調用特定的HTTP處理程序相匹配時的一個子集。一些上了年紀的正則表達式的都無法訪問（例如a.c* ⊃ abc*），我想他們修剪。確定一個正則表達式是否是另一個

有沒有一個庫，給出了兩個正則表達式會告訴我，如果第二個是第一個子集？

我不確定這個起初是否可以確定（它聞起來像一個不同的名稱，暫停問題）。但事實證明，it's decidable。

來源

2013-09-10 deft_code

不完全確定我明白 - 你是說你有兩個正則表達式，'a.c *'和'abc *'？如果它們是相同的，或者部分相同，你不想破譯它們嗎？或者是'a.c *⊃abc *'整個正則表達式？因爲我從來沒有在 – SmokeyPHP

之前看到這個符號，所以意味着嚴格的超集，我可能應該使用⊇，這更常見。我試圖說''abc *'接受的每個字符串也被'a.c *'接受 –

您對Regex的定義是什麼？在大多數編程語言中，正則表達式語法通常允許反向引用，它比常規語言更強大。因此，納入的可判定性甚至不明確...... –

在數學部分有一個答案：https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another。

基本思想：

計算的最小DFA兩種語言。
計算自動化M1和M2的叉積，這意味着每個狀態由一對[m1，m2]組成，其中m1來自M1，M2來自M2，適用於所有可能的組合。新的轉換F12是：F12（[m1，m2]，x）=> [F1（m1，x），F2（m2，x）]。這意味着，如果有從狀態M1中M1的過渡到M1' ，而從狀態平方米讀取x和在M2至M2' ，而讀X，則有在M12爲[M1' 一種過渡從[M1，M2]，M2' ]閱讀x。
在最後你看到可到達的狀態：
- 如果有一對[接受，拒絕]，則M2不是M1的一個子集
- 如果有一對[拒絕，accapting]那麼M1不M2
的

一個子集，這將是benificial如果你只是計算新過渡，結果狀態，從一開始就忽略所有非可到達的狀態。

來源

2013-09-17 21:41:36

Trying to find the complexity of this problem lead me to this paper.

問題的正式定義可以內找到：此一般被稱爲納入問題

對於R納入問題，是測試兩個給定表達式R， R'∈R，是否ř⊆R'。

該論文有一些偉大的信息（總結：除了最簡單的表達式是相當複雜），然而搜索上包括問題的信息導致一個直接回StackOverflow。這個問題的答案已經有了一個鏈接到a paper describing a passable polynomial time algorithm應涵蓋了很多常見的情況。

來源

2013-09-18 05:31:56

如果正則表達式使用允許接受不常規語言的典型過程匹配器（如Perl，Java，Python，Ruby等中的那些）的「高級特性」，那麼您運氣不好。問題一般是不可判定的。例如。一個下推自動機是否可以識別相同的情況下自由（CF）語言，另一種是不可判定的問題。擴展正則表達式可以描述CF語言。另一方面，如果正則表達式在理論意義上是「真實的」，僅由串聯，交替和Kleene星形組成的有限字母表的字符串加上通常的語法糖（字符類， +，？等），那麼就有一個簡單的多項式時間算法。

我不能給你的庫，但這樣的：

For each pair of regexes r and s for languages L(r) and L(s) 
    Find the corresponding Deterministic Finite Automata M(r) and M(s) 
    Compute the cross-product machine M(r x s) and assign accepting states 
     so that it computes L(r) - L(s) 
    Use a DFS or BFS of the the M(r x s) transition table to see if any 
     accepting state can be reached from the start state 
    If no, you can eliminate s because L(s) is a subset of L(r). 
    Reassign accepting states so that M(r x s) computes L(s) - L(r) 
    Repeat the steps above to see if it's possible to eliminate r

轉換正則表達式到DFA一般使用湯普森的建設得到一個非確定性自動機。這會使用子集構造轉換爲DFA。交叉產品機器是另一種標準算法。

這一切都是在20世紀60年代制定的，現在是任何優秀的本科計算機科學理論課程的一部分。該主題的黃金標準是Hopcroft and Ullman, Automata Theory。

來源

2013-09-22 01:51:53 Gene

我找到了一個提供集合操作的python正則表達式庫。

http://github.com/ferno/greenery

證明說：Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {}。

import sys 
from greenery.lego import parse 

subregex = parse(sys.argv[1]) 
supregex = parse(sys.argv[2]) 

s = subregex&(supregex.everythingbut()) 
if s.empty(): 
    print("%s is a subset of %s"%(subregex,supregex)) 
else: 
    print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s)

例子：

subset.py abcd.* ab.* 
abcd.* is a subset of ab.* 

subset.py a[bcd]f* a[cde]f* 
a[bcd]f* is not a subset of a[cde]f*, it also matches abf*

，因爲你需要使用最少的DFA在爲了這個其他的答案提到的庫可能不可靠，我可以用Python庫實現這個工作。我不確定ferno's庫使得（或可以）保證。

順便說一句：玩圖書館來計算逆或簡化正則表達式很有趣。
a(b|.).*簡化爲a.+。這是非常小的。
abf*的倒數是([^a]|a([^b]|bf*[^f])).*|a?。試着自己想出來！

來源

2013-09-25 19:12:06

該庫並不能保證生成最小的DFA，但我不認爲所討論的DFA需要最小限度才能得到正確的答案。 – qntm

您是否看到[reduce（）]（https://github.com/ferno/greenery#fsmreduce）？ –

確定一個正則表達式是否是另一個

回答

相關問題