比如对于 123abc，123abc 比 /d+abc 更精确，而 /d+abc 比 /d+/w+更精确，我也不好这里的精确的定义
This topic created in 2329 days ago, the information mentioned may be changed or developed.
 |
1
geelaw Jan 10, 2020  1
你可以定义表达式 A 比表达式 B 更精确当且仅当 A 识别的语言是 B 识别的语言的子集。这个序不是全序。
判断两个表达式是否等价 和 判断一个是否比另一个更精确 是 poly-time Turing 归约等价的，前者是 PSPACE-complete，所以不要指望一个快速的算法。 实践中，如果你的表达式很小，要判断 A 是否比 B 更精确，可以看 A 交 B 的最小 DFA 和 A 的最小 DFA 是否等价，这需要指数时间。 |
Select Language