如何用程序判断对与同一个字符串，哪个正则对于这个字符串匹配地更’精确’

[zhoudaiyu]

比如对于 123abc，123abc 比 /d+abc 更精确，而 /d+abc 比 /d+/w+更精确，我也不好这里的精确的定义

[geelaw]

你可以定义表达式 A 比表达式 B 更精确当且仅当 A 识别的语言是 B 识别的语言的子集。这个序不是全序。

判断两个表达式是否等价 和 判断一个是否比另一个更精确 是 poly-time Turing 归约等价的，前者是 PSPACE-complete，所以不要指望一个快速的算法。

实践中，如果你的表达式很小，要判断 A 是否比 B 更精确，可以看 A 交 B 的最小 DFA 和 A 的最小 DFA 是否等价，这需要指数时间。

[zhoudaiyu]

@geelaw 感谢！请问 A 交 B 的 DFA 是什么意思？是两个 dfa 的交集吗？编译原理忘了)