代码之家 › 专栏 › 技术社区 › Akshatha Mandadi

在{0,1}上构造占用字符串的nfa,使某些两个0被长度为4i,i>=0的字符串分隔

automata-theory non-deterministic computation-theory finite-automata

1

Akshatha Mandadi · 技术社区 · 8 年前

我试图通过首先为长度为4i的字符串设计一个NFA来解决这个问题,因为它的形式是0(mod 4)。

状态数=4,我刚刚添加了另外两个状态,在这个设计的每一端各添加一个,并在0上进行了转换,现在状态数=6。当我尝试检查时,我的解决方案是错误的。有人能解释一下我哪里出了问题吗?

1 回复 | 直到 8 年前

1

roctothorpe 8 年前

这个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 -在检查两个0之间的字符串长度是否为4的倍数的NFA循环中,对该字符串的内容没有限制。具体来说,没有理由说这个字符串的第一个字符不能是0(从q1到q5的转换)。
010100111 (和/或 0101001110 , 0101000 )-这些都是字符串示例,其中两个0由一个长度为4i的字符串分隔,后跟一些其他字符。您的NFA也应该接受这些字符串,但目前不接受-请记住,如果饰面在接受状态下,如果NFA需要进行转换,但不存在转换,那么它将死亡,并且该路径将拒绝。

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