algorithm - DFA - 设计一个 DFA 接受超过 {0,1} 的所有字符串，最多包含两个 0 0's and three 11' 作为子字符串

Question

我正在练习我的 DFA，我遇到了这个似乎非常复杂的问题。我试着把它分成两个较小的问题，我有一个答案，但它看起来不适合我。

有人可以帮助我，或者至少给我一些提示。

顺便说一下，它们都是接受状态。

我能想到的另一种可能性是，你只有每两个 O 或 1 的接受状态，因为它们需要成对。因此，例如 11 接受 11 接受 11 接受。

Answer 1

您将您的状态机描述为一幅巨大的图画，但您可以通过使用结构化名称命名您的状态来简化您的问题，而不是试图绘制一张巨大的图表。

让你的状态为 (n, m, s) 其中 n 是你看到的 00 的数量，m 是你看到的 11 的数量，s 是前一个字符读取 (s='', ' 1', '0')(其中 '' 表示您没有看到之前的字符，或者您刚刚找到了 '00' 或 '11')。

那么你的转换是:

(n, m, '')  -0-> (n, m, '0')
(n, m, '')  -1-> (n, m, '1')
(n, m, '0') -0-> (n+1, m, '')
(n, m, '0') -1-> (n, m, '1')
(n, m, '1') -0-> (n, m, '0')
(n, m, '1') -1-> (n, m+1, '')

所有 n<=2 和 m<=3 的状态都在接受。开始状态是 (0, 0, '')。

这不是有限的，但您可以通过将所有非接受状态合并为一个状态来实现。它将有 (3 * 4 * 3 + 1) = 37 个状态，这是最小的。

计算重叠的 00 和 11。

上面的答案假设'000'包含一个'00'而不是2个'00'(即'00'的数量是字符串中非重叠'00'的最大数量，对于' 11').如果你想把'000'算作2，你需要这台机器:

状态是 S(开始)或(n、m、s)，其中 n、m 与之前相同，s 是“0”或“1”。然后:

S -0-> (0, 0, '0')
S -1-> (0, 0, '1')
(n, m, '0') -0-> (n+1, m, '0')
(n, m, '0') -1-> (n, m, '1')
(n, m, '1') -0-> (n, m, '0')
(n, m, '1') -1-> (n, m+1, '1')

除 n>2 或 m>3 的状态外，所有状态都在接受。同样，我们将所有非接受状态合并为一个状态。

这有 (3 * 4 * 2 + 2) = 26 个状态，这也是最小的。

生成 FSM 图。

根据正式描述，可以编写程序生成描述机器的 DOT 文件。这是在答案的第一部分为机器生成图表的程序。 (请注意，它没有显示哪些状态正在接受，但除了 FAIL 之外它们都是)。

def state(n, m, s):
    if n > 2 or m > 3: return 'FAIL'
    return "n%s_%s_%s" % (n, m, s)

def T(st, c):
    n, m, s = st
    if s == '':
        return (n, m, c)
    if s == '0':
        return (n+1, m, '') if c=='0' else (n, m, c)
    if s == '1':
        return (n, m+1, '') if c=='1' else (n, m, c)

print 'digraph {'
for n in xrange(3):
    for m in xrange(4):
        for s in ['', '0', '1']:
            for c in '01':
                print '    %s -> %s [label="%s"]' % (state(n, m, s), state(*T((n, m, s), c)), c)

print '}'

这是通过 dot -Tpng 管道输出的结果: