regex - 你可以跳过联合表达式中的 epsilon 转换吗（汤普森的构造算法）

Question

在下图中，我可以同时使用这两种 NFA 吗？如果不是那为什么？

Answer 1

是的，它们是等价的（它们识别相同的语言）。更正式地说：

首先，让我们为您的州命名：

现在，通过powerset 构造，让我们删除 epsilon 转换：

最后，我们可以使用任何 DFA 最小化算法，例如Brzozowski 的（反转箭头，再次应用幂集构造，重新反转箭头）来获得最终的 DFA。