如何判断一个正则表达式是否匹配另一个正则表达式的子集？
我只是想知道，是否可以用一个正则表达式去匹配另一个正则表达式，也就是说，能不能做到这样的事情：
['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>
但我在想，正则表达式是否有能力去匹配其他一些不那么具体的表达式，就像我上面试图解释的那样，b到x之间的任何字母总是会是a到z之间任何字母的一个子集（匹配）。我知道仅仅通过调用一个编译好的表达式去匹配另一个编译好的表达式是做不到的，但问题依然是：这真的可能吗？
如果这仍然不清楚，请告诉我。
7 个回答
除了antinome的回答之外：
很多不属于基本正则表达式定义的构造，实际上还是可以被称为正则的，并且在解析正则表达式后可以进行转换（需要用真正的解析器，因为正则表达式的语言本身并不属于正则）：比如把 (x?) 转换成 (x|)，把 (x+) 转换成 (xx*)，还有像 [a-d] 这样的字符类可以转换成它们对应的并集 (a|b|c|d) 等等。所以你可以使用这些构造，同时也能测试一个正则表达式是否匹配另一个正则表达式的子集，这个可以用antinome提到的DFA比较来实现。
不过，有些构造，比如回溯引用，是不属于正则的，无法用NFA或DFA来表示。
即使是看似简单的测试一个带回溯引用的正则表达式是否匹配特定字符串的问题，也是NP完全的（http://perl.plover.com/NPC/NPC-3COL.html）。
用户 "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.
我觉得——理论上来说——要判断正则表达式 A 是否匹配正则表达式 B 匹配的内容的一个子集，可以用以下算法：
- 计算出正则表达式
B的最小确定性有限自动机（DFA），还有A|B的“并集”的 DFA。 - 检查这两个 DFA 是否相同。如果相同，那么
A就是B匹配内容的一个子集。
不过，实际上要做到这一点可能会是个大工程。有一些解释，比如 从正则表达式构建最小状态 DFA，但这些通常只考虑数学上纯粹的正则表达式。你还需要处理 Python 为了方便而添加的一些扩展。此外，如果这些扩展导致语言变得不规则（我不确定是否会这样），那么你可能就无法处理这些情况了。
不过，你到底想做什么呢？也许有更简单的方法……？