确定正则表达式是否是另一个的子集

Question

我有一个庞大的正则表达式集合,当匹配时调用一个特定的http处理程序.一些较旧的正则表达式是无法访问的(例如a.c* ? abc*),我想修剪它们.

是否有一个库给出两个正则表达式会告诉我第二个是否是第一个的子集？

我一开始并不确定这是否具有可判定性(它的气味就像一个不同名称的停止问题).但事实证明它是可判定的.

Answer 1

试图找到这个问题的复杂性引导我阅读本文.

可以在以下内容中找到问题的正式定义:这通常称为包含问题

R的包含问题是测试两个给定的表达式r,r'∈R,是否r⊆r'.

那篇论文有一些很好的信息(摘要:除了最简单的表达式之外的所有表达都相当复杂),但是搜索包含问题的信息会直接导致StackOverflow.这个答案已经链接到描述可通过多项式时间算法的论文,该算法应涵盖许多常见情况.

Answer 2

如果正则表达式使用典型程序匹配器(如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通常使用Thompson的结构来获得非确定性自动机.使用子集构造将其转换为DFA.跨产品机器是另一种标准算法.

这一切都是在1960年代制定的,现在已成为任何优秀的本科计算机科学理论课程的一部分.该主题的黄金标准是Hopcroft和Ullman,Automata Theory.

Answer 3

我找到了一个提供集合操作的 python regex 库。

http://github.com/ferno/greenery

证据说Sub ? Sup ? Sub ? ¬Sup is {}。我可以用 python 库实现这个：

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 才能使其正常工作。我不确定ferno 的图书馆能（或能不能）做出这样的保证。

顺便说一句：使用库来计算逆或简化正则表达式很有趣。
a(b|.).*简化为a.+. 这是非常小的。
的倒数abf*是([^a]|a([^b]|bf*[^f])).*|a?。尝试自己想出这个！

Answer 4

数学部分有答案：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)]。这意味着，如果在读取 x 时 M1 中存在从状态 m1 到 m1' 的转换，并且在读取 x 时 M2 中存在从状态 m2 到 m2' 的转换，则 M12 中存在从 [m1, m2] 到 [m1', m2' 的转换] 阅读 x 时。
• 最后，您查看可到达的状态：
  • 如果存在一对[接受，拒绝]，则 M2 不是 M1 的子集
  • 如果存在一对 [rejecting, accapting]，则 M1 不是 M2 的子集

如果您只计算新的转换和结果状态，从一开始就忽略所有不可到达的状态，那将是有益的。