我得到了一个正则表达式，我想将其转换为 NFA，然后是 DFA。这是正则表达式：
a ( b | c )* a | aac* b
然后我使用汤姆森算法将其转换为 NFA：
这是DFA：
有人可以快速看一下让我知道我是错还是对？
问问题
488 次
1 回答
4
由于这很可能是家庭作业，因此我很犹豫是否给您完整的正确解决方案。
您的 NFA 看起来是正确的，但有许多不必要的多余状态，但不会对其正确性产生不利影响。（乍一看，您似乎可以删除 11 个状态。）
但是，您的 DFA 不正确。这是因为当您开始处理字符串的一个或另一个条件时，您稍后会将它们重新连接在一起。这允许它从一个接受的字符串匹配中获取路径a(b|c)*a并获取另一个b或c通过移动到节点15,17或11. 然后，即使它与您的表达式不匹配，它也会接受此字符串。
您需要做的基本上是阻止这种情况发生。如果您还有其他问题，请随时提出。
我强烈建议列出你知道应该接受和不应该接受的测试字符串，然后跟踪它们，确保你的自动机以正确的（接受或拒绝）状态结束。
于 2011-03-05T18:18:37.723 回答