1

问题：

定义一个 DFA，它接受 {0,1} 上的所有字符串，这样五个连续位置的每个块都至少包含两个 0。请仔细阅读问题。问问自己：这是否允许 e (epsilon (empty string)) 被接受？0101怎么样？这样的英文描述可以在各种书籍中找到，我想确保您知道如何阅读和解释。

讲师提示：““5 块”DFA 可以通过编程方式轻松生成。我两种方式都可以（手动和编程方式）。因为我擅长 Emacs 和键盘宏，我什至可以手动完成' 机械且相当快。但程序化不太容易出错且紧凑。“

我把这件事画出来了，我认为我做错了，因为它已经失控了。

我在 python 中制作 DFA 之前的草图： 在此处输入图像描述

但是，这是不对的，因为索引 2、3、4、5 和 6 构成了一个由五个连续位置组成的块，所以我需要在其中考虑至少两个零。哦，太好了，我一直认为它需要两个 1，而不是两个 0。我会以完全错误的方式解决这个问题吗？因为按照我的想法，这将有大量的状态。

（回到画这个大的 DFA）

4

3 回答 3

2

我要解决的方法是为每个可能的 5 位字符串定义一个状态，代表看到的最后 5 位。从代表 00000 的状态开始，自然地从一个状态移动到另一个状态，并用 2 个或多个零标记每个状态为接受。

于 2012-09-17T04:43:46.587 回答
1

如果你想用老派的方式来做：

def check(s):
    buffer = s[:5]
    i = 5
    count0, count1 = 0, 0
    while i < len(s):
        if len(buffer) == 5:
            first = buffer[0]
            if first == '0':
                count0 -= 1
            else:
                count1 -= 1
            buffer = buffer[1:]
        buffer += s[i]
        if buffer[-1] == '0':
            count0 += 1
        else:
            count1 += 1
        if count0 < 2:
            return "REJECT"
        i += 1
    if buffer.count('0') >= 2:
        return "ACCEPT"
    else:
        return "REJECT"

稍微聪明一点的方法：

def check(s):
    return all(ss.count('0')>=2 for ss in (s[i:i+5] for i in xrange(len(s)-4)))

上述方法的详细代码：

def check(s):
    subs = (s[i:i+5] for i in xrange(len(s)-4))
    for sub in subs:
        if sub.count('0') < 2:
            return "REJECT"
    return "ACCEPT"

尚未测试此代码，但它应该可以工作。你的教授可能想要第三种方法。

希望这可以帮助

于 2012-09-17T04:33:35.207 回答
1

实际上有11 16 个状态，包括单个拒绝状态。这些状态对应于最多四个字符的历史记录，在最近的第二个零处被截断。只需要四个字符，因为转换构成了块中的第五个字符；如果转换字符不是 0 并且四字符历史中没有两个零，则转换失败。

我手动生成了转换，因为键入比编写 Python 更快，所以我将把广义 (k, n)（n 块中的 k 个零）问题留作编码练习。（我在州名中插入了 x 以使其更好地排列。）

sxx00 (0)->sxx00 (1)->sx001
sx001 (0)->sx010 (1)->s0011
sx010 (0)->sxx00 (1)->s0101
s0011 (0)->s0110 (1)->s0111
s0101 (0)->sx010 (1)->s1011
s0110 (0)->sxx00 (1)->s1101
s0111 (0)->s1110 (1)->sFAIL
s1011 (0)->s0110 (1)->sFAIL
s1101 (0)->sx010 (1)->sFAIL
s1110 (0)->sxx00 (1)->sFAIL
sFAIL (0)->sFAIL (1)->sFAIL

[编辑]：这实际上不太正确，因为（当我阅读问题时）应该接受字符串 '1111'。（其中每个五个字符的块都有两个零，很简单，因为没有五个字符的块。）所以还有一些额外的启动状态：

start (0)->sxx00 (1)->s1
s1    (0)->sx010 (1)->s11
s11   (0)->s0110 (1)->s111
s111  (0)->s1110 (1)->s1111
s1111 (0)->sFAIL (1)->sFAIL

看起来很像 sFAIL 的最后一个状态是不同的，因为它是一个接受状态。

于 2012-09-17T04:56:21.093 回答