如何判断一个正则表达式是否与另一个正则表达式的子集匹配？

Question

我只是想知道是否可以使用一个正则表达式来匹配另一个,这是某种形式:

['a-z'].match(['b-x'])
True

['m-n'].match(['0-9'])
False

这种事情是否可以与正则表达式一起使用？我正在使用python工作,所以任何特定于re模块实现的建议都会有所帮助,但我会接受有关正则表达式的任何建议.

编辑:好的,有些澄清显然是有序的!我肯定知道正常的匹配语法看起来像这样:

expr = re.compile(r'[a-z]*')
string = "some words"
expr.match(string)
<sRE object blah blah>

但我想知道正则表达式是否能够匹配我在上面尝试解释的非语法正确版本中的其他不太具体的表达式,来自bx的任何字母始终是来自az的任何字母的子集(匹配).我知道只是从尝试这不是你可以通过在另一个编译表达式上调用一个已编译表达式的匹配来做的事情,但问题仍然存在:这是否可能？

如果这还不清楚,请告诉我.

Answer 1

我认为 - 从理论上讲 - 判断regexp是否A匹配正则表达式匹配的子集B,算法可以:

1. 计算B"联合" 的最小确定性有限自动机A|B.
2. 检查两个DFA是否相同.当且仅当A匹配B匹配的子集时才是这样.

但是,在实践中这可能是一个重要的项目.有一些解释,例如从正则表达式构造最小状态DFA,但它们只倾向于考虑数学上纯的正则表达式.为了方便起见,您还必须处理Python添加的扩展.此外,如果任何扩展导致语言不规则(我不确定是否是这种情况),您可能无法处理这些.

但是你想做什么？也许有一种更简单的方法......？

Answer 2

除了antinome的回答:

许多不属于基本的正则表达式定义的一部分结构的仍然是常规的,并且可以解析正则表达式后转换(与真实的解析器,因为正则表达式的语言不是正规本身):(x?)对(x|),(x+)对(xx*),人物类,如[a-d]以其相应的工会(a|b|c|d)等,所以可以使用这些结构仍然测试一个正则表达式是否使用antinome提到的DFA相比其他正则表达式的一个子集相匹配.

某些构造(如后引用)不是常规构造,也不能由NFA或DFA表示.

甚至看似简单的测试带有后引用的正则表达式是否与特定字符串匹配的问题是NP-complete(http://perl.plover.com/NPC/NPC-3COL.html).

Answer 3

使用两个正则表达式"antinome"验证帖子:55*和5*:

REGEX_A:55*[匹配"5","55","555"等,不匹配"4","54"等]

REGEX_B:5*[匹配"","5""55","555"等,不匹配"4","54"等]

[这里我们假设55*不是含蓄的.55.*和5*不是.5.* - 这就是为什么5*不匹配4]

REGEX_A可以具有如下NFA:

  {A}--5-->{B}--epsilon-->{C}--5-->{D}--epsilon-->{E}
           {B} -----------------epsilon --------> {E} 
                          {C} <--- epsilon ------ {E}

REGEX_B可以具有如下NFA:

  {A}--epsilon-->{B}--5-->{C}--epsilon-->{D}
  {A} --------------epsilon -----------> {D} 
                 {B} <--- epsilon ------ {D}

现在我们可以得到(REGEX_A | REGEX_B)的NFA*DFA,如下所示:

  NFA:
  {state A}  ---epsilon --> {state B} ---5--> {state C} ---5--> {state D}
                                              {state C} ---epsilon --> {state D} 
                                              {state C} <---epsilon -- {state D}
  {state A}  ---epsilon --> {state E} ---5--> {state F}
                            {state E} ---epsilon --> {state F} 
                            {state E} <---epsilon -- {state F}

  NFA -> DFA:

       |   5          |  epsilon*
   ----+--------------+--------
    A  |  B,C,E,F,G   |   A,C,E,F
    B  |  C,D,E,F     |   B,C,E,F
    c  |  C,D,E,F     |   C
    D  |  C,D,E,F,G   |   C,D,E,F
    E  |  C,D,E,F,G   |   C,E,F
    F  |  C,E,F,G     |   F
    G  |  C,D,E,G     |   C,E,F,G

                    5(epsilon*)
    -------------+---------------------
              A  |  B,C,E,F,G 
      B,C,E,F,G  |  C,D,E,F,G 
      C,D,E,F,G  |  C,D,E,F,G 

    Finally the DFA for (REGEX_A|REGEX_B) is:
         {A}--5--->{B,C,E,F,G}--5--->{C,D,E,F,G}
                                     {C,D,E,F,G}---5--> {C,D,E,F,G}

         Note: {A} is start state and {C,D,E,F,G} is accepting state. 

同样,REGEX_A(55*)的DFA是:

       |   5    |  epsilon*
   ----+--------+--------
    A  | B,C,E  |   A
    B  | C,D,E  |   B,C,E
    C  | C,D,E  |   C
    D  | C,D,E  |   C,D,E
    E  | C,D,E  |   C,E


            5(epsilon*)
   -------+---------------------
       A  |  B,C,E  
   B,C,E  |  C,D,E
   C,D,E  |  C,D,E

    {A} ---- 5 -----> {B,C,E}--5--->{C,D,E}
                                    {C,D,E}--5--->{C,D,E}
Note: {A} is start state and {C,D,E} is accepting state

同样,REGEX_B(5*)的DFA是:

       |   5    |  epsilon*
   ----+--------+--------
    A  | B,C,D  |   A,B,D
    B  | B,C,D  |   B
    C  | B,C,D  |   B,C,D
    D  | B,C,D  |   B,D


            5(epsilon*)
   -------+---------------------
       A  |  B,C,D  
   B,C,D  |  B,C,D

    {A} ---- 5 -----> {B,C,D}
                      {B,C,D} --- 5 ---> {B,C,D}
Note: {A} is start state and {B,C,D} is accepting state

结论:

DFA of REGX_A|REGX_B identical to DFA of REGX_A 
      -- implies REGEX_A is subset of REGEX_B
DFA of REGX_A|REGX_B is NOT identical to DFA of REGX_B 
      -- cannot infer about either gerexes.