regex - 如何将 (ab u aab u aba)* 转换为 NFA？

Question

(ab u aab u aba)*

我做到了，但我想要一些关于其正确性的反馈：

如果正确：我们可以进一步简化 (ab u aab u aba)* 吗？

如果没有：我错过了什么？

编辑：似乎我缺少从所有 3 个最终状态回到初始状态的电子转换，我需要一个初始和最终状态的新状态，它将在电子转换时进入旧的初始状态。（克莱恩星规则）。

PS我们也可以简化(a u b)*aabab和(a u b)*a(a u b)(a u b)(a u b)(a u b)。

我之所以问是因为如果没有办法简化/最小化，那将是一个非常长的 DFA ......

Answer 1

我可以看到您的第一个案例的一个小简化，您可以将其写为 (a(bu ab u ba))* 但这并不一定有帮助。我仍然猜想你的 DFA 不需要你想象的那么多状态。

后两种情况都需要具有 32 个状态的 DFA，以便跟踪读取的最后 5 个字符。不同之处在于第二个 DFA 只有一个终端状态，而第三个 DFA 有 16 个。