我应该构建一个接受的 DFA
{ w | w 是一个单词,除了 'aa' 和 'aaa' }
这是正确的解决方案吗?粗线状态应该是结束状态。
编辑
抱歉,不知何故混合了两种不同的练习。已更正。
编辑 2
这是更正的解决方案(?)!
我将完整保留下面的答案,因为它在上下文中很有用。
随着您对问题的更新,以及您对提议的解决方案的进一步更新,在我看来它是有效的。做得好!
=========出于历史目的的旧帖子===========
重要提示: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 - 重置你。连续两次,你失败了:(