我说得对吗？ （有限自动机）

Question

我得到了一个正则表达式，我打算将其转换为 NFA，然后转换为 DFA。这是正则表达式：

a ( b | c )* a | a a c* b

然后我使用 Thomson 算法将其转换为 NFA：

这是 DFA：

有人可以快速看一下让我知道我是错还是对吗？

Answer 1

由于这很可能是家庭作业，因此我犹豫是否要给您完整的正确解决方案。

您的 NFA 看起来是正确的，但有很多不必要的多余状态，但不会对其正确性产生不利影响。 （乍一看似乎可以删除 11 个州。）

不过，您的 DFA 是不正确的。这是因为当您分支开始处理字符串的一个条件或另一个条件时，稍后将它们重新连接在一起。这允许它从匹配

a(b|c)*a

的接受字符串中获取路径，并通过移动到节点

b

或

c

来获取另一个

15,17

或

11

。然后它接受这个字符串，即使它与您的表达式不匹配。

你需要做的基本上就是阻止这种情况发生。如果您还有其他问题，请随时提问。

我强烈建议您制作一个您知道应该接受和不应该接受的测试字符串列表，然后跟踪它们，确保您的自动机以正确的（接受或拒绝）状态结束。

Answer 2

我可以将所有计算电子关闭和移动吗？