1

给定的图像有我对问题的解决方案，这是错误的我试图通过首先为长度为 4i 的字符串设计一个 NFA 来解决这个问题，因为它的形式是 0(mod 4)。

状态数 = 4，我刚刚添加了 2 个其他状态，本设计的每一端各一个，并在 0 上进行了转换，现在状态数 = 6。当我尝试检查时，我的解决方案是错误的。有人可以解释我哪里出错了吗？

4

1 回答 1

1

这个 NFA 的高级设计是正确的，只是缺少一些细节。我发现在设计 NFA 时有用的一个策略是首先提出一组测试用例或测试字符串。也就是说，如果我正在编写一个程序来检查一个字符串是否满足这些特定属性，我会测试哪些字符串？边缘情况会是什么？这些可以帮助您在第一次设计 NFA 时发现模式，然后您可以使用它们来检查您的工作。

例如，这里有一些我会检查这个问题的测试用例：

00              \\ i = 0
010100          \\ i = 1
0101011010      \\ i > 1, handles lengths of larger multiples of 4
011110, 000000  \\ it shouldn't matter what's in between the two 0s
111010100       \\ can have anything before the two 0s 
010100111       \\ can have anything after the two 0s
... etc...

你应该特别考虑这两个：

  • 000000- 在你的 NFA 循环中检查两个 0 之间的字符串长度是否是 4 的倍数，这个字符串的内容没有限制。具体来说，这个字符串的第一个字符没有理由不能是 0（从 q1 到 q5 的转换）。
  • 010100111(和/或0101001110, 0101000) - 这些都是字符串示例，其中我们有两个 0，由长度为 4i 的字符串分隔，后跟一些其他字符。这些字符串也应该被您的 NFA 接受，但目前不接受 - 请记住，如果 NFA在接受状态下完成，则 NFA 接受，并且如果 NFA 需要进行转换并且不存在转换，它就会死亡并且该路径拒绝。

您是否看到可以进行哪些修改来解决这些问题？

于 2018-01-07T19:53:39.907 回答