如何用程序判断对与同一个字符串，哪个正则对于这个字符串匹配地更’精确’
zhoudaiyu · 2020-01-10 18:10:19 +08:00 via iPhone · 905 次点击这是一个创建于 1810 天前的主题，其中的信息可能已经有所发展或是发生改变。
比如对于 123abc，123abc 比 /d+abc 更精确，而 /d+abc 比 /d+/w+更精确，我也不好这里的精确的定义
 |
1
geelaw 2020-01-10 18:18:15 +08:00  1
你可以定义表达式 A 比表达式 B 更精确当且仅当 A 识别的语言是 B 识别的语言的子集。这个序不是全序。
判断两个表达式是否等价 和 判断一个是否比另一个更精确 是 poly-time Turing 归约等价的，前者是 PSPACE-complete，所以不要指望一个快速的算法。 实践中，如果你的表达式很小，要判断 A 是否比 B 更精确，可以看 A 交 B 的最小 DFA 和 A 的最小 DFA 是否等价，这需要指数时间。 |
Select Language