1

我应该构建一个接受的 DFA

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

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

编辑

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

编辑 2

这是更正的解决方案(?)!

4

1 回答 1

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 - 重置你。连续两次,你失败了:(

于 2011-02-22T18:24:49.547 回答