finite-automata - 这个 DFA 是否正确？

Question

我应该构建一个接受的 DFA

{ w | w 是一个单词，除了 'aa' 和 'aaa' }

这是正确的解决方案吗？粗线状态应该是结束状态。

编辑

抱歉，不知何故混合了两种不同的练习。已更正。

编辑 2

这是更正的解决方案（？）！

Answer 1

我将完整保留下面的答案，因为它在上下文中很有用。

随着您对问题的更新，以及您对提议的解决方案的进一步更新，在我看来它是有效的。做得好！

=========出于历史目的的旧帖子===========

重要提示：aa 是 aaa 的子字符串。因此，通过排除 aa，您会自动排除 aaa 和 aaaa 和 aaaaa。这意味着您只能连续拥有 1 个 a。

因此，无论何时添加 a，都需要进入接受状态。每当您在此之后添加 a 时，您都需要进入一个无论如何都会永远循环的非接受状态。

下面是我想出的。我不建议只是...放下它。想想这个。这些问题对训练你的思维方式非常重要！！！不要宠坏自己！

S 表示开始状态 + on corner 表示接受状态 X on corner 表示不接受状态

 B  +-+  A   +-+  A   X-X  A | B
+---|S| ---> |1| ---> |2| ------+
|   +-+      +-+      X-X       |
+___^ ^___B___|       ^________+

"" - ends on start - okay 
"B" - ends on start - okay 
"A" - ends on 1 - okay 
"AA" - ends on 2 - not accepted 
"BAA" - Stats on S, goes to S, goes to 1, goes to 2 - not accepted.

A - 让你走向失败。B - 重置你。连续两次，你失败了:(