regex - 无法为某些正则表达式构造四态 NFA

Question

在一个关于 NFA 的练习中，我被要求在正则表达式 (aa|aab)*b 上构建一个四态 NFA。我尝试自己构建它，我只能找到一个 5-state NFA，后来在线工具证实了这一点。

（我发现它没有（4）是最终的，并且没有从 b 的（3）到（2）的附加箭头，但这导致相同）是我没有看到问题，还是没有办法做这只有四个州？

Answer 1

您已选择创建一个 DFA（我也不知道如何创建一个只有 4 个状态的 DFA）。但是，您可以构建NFA，这意味着您可以使用同一个字母进行多个转换。

因此，您可以省略状态 (2)，b将从 (0) 到 (2) 的 -edge 移动到 (4)，并使用b从 (3) 到 (0) 的字母引入新边。这意味着当在两秒b后读取 a 时a，您可以转换到最终状态或回到开头。