我说得对吗？ （有限自动机）
我得到了一个正则表达式，我应该将其转换为 NFA，然后转换为 DFA。这是正则表达式：
a ( b | c )* a | aac* b
然后我使用 Thomson 算法将其转换为 NFA： 
这是 DFA： 
有人可以快速浏览一下让我知道我是错还是对吗？
I was given a regular expression, and I am suppose to covert it to NFA and then DFA. Here's the regular expression:
a ( b | c )* a | a a c* b
Then I coverted this to NFA using Thomson's algorithm:
and here's the DFA:
Can someone please take a quick look at let me know if I am wrong or right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于这很可能是家庭作业，因此我犹豫是否要给您完整的正确解决方案。
您的 NFA 看起来是正确的，但有很多不必要的多余状态，但不会对其正确性产生不利影响。 （乍一看，您似乎可以删除 11 个州。）
不过，您的 DFA 是不正确的。这是因为当您分支开始处理字符串的一个条件或另一个条件时，稍后将它们重新连接在一起。这允许它从匹配
a(b|c)*a的接受字符串中获取路径，并通过行进获取另一个b或c到节点15,17或11。然后它接受该字符串，即使它与您的表达式不匹配。您需要做的基本上就是阻止这种情况发生。如果您还有其他问题，请随时提问。
我强烈建议您制作一个您知道应该接受和不应该接受的测试字符串列表，然后跟踪它们，确保您的自动机以正确的（接受或拒绝）状态结束。
Since this is very likely homework, I'm hesitant to just give you the complete correct solution.
Your NFA appears correct, but has a lot of superfluous states that aren't necessary but do not adversely affect its correctness. (At first glance it looks like you could remove 11 states.)
Your DFA is incorrect, though. This is because when you branch off to begin handling one condition of the string or the other, you later rejoin them together. This allows it to take the path from an accepted string matching
a(b|c)*aand take in anotherborcby travelling to nodes15,17or11. It then accepts this string even though it doesn't match your expression.What you need to do is basically stop this from happening. If you have additional questions feel free to ask.
I highly recommend making a list of test strings that you know should be and shouldn't be accepted, and then trace them through, making sure your automata ends in the correct (accept or reject) state.