regular-language - RE和有限自动机相同吗？

Question

我想了解 RE a∗ba∗ab∗ 是否与以下有限自动机相同。我感到困惑的部分是，从 state 3 到 state 4 ，有 ab ，这意味着该语言需要在末尾有 ab ，而RE只有 b* ，这意味着 0 或更多 b 。如果不是这个 RE 的正确有限自动机是什么？

标签： regular-languagefinite-automatacomputation-theory

Answer 1

实际上，正则表达式a*ba*ab*并不等同于您在问题中陈述的原因所显示的 DFA。

Thompson 算法是将正则表达式系统地转换为 NFA 的标准方法。（如果您需要确定性有限自动机，则可以运行子集构造。）