DFA

Question

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

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

顺便说一句，他们都在接受状态。

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

Answer 1

好吧，你可以用文字描述它，而不是画自动机。

我将如何解决您的问题：让一个顶点成为一个三元组，其中

第一个元素是 0、1、2、3，"at least 4" 表示 11 的个数。
第二个元素是 0、1、2 和 "at least 3" 取决于“00”的数量
第三个元素是最后一个符号（0、1或"string is empty"）

定义转换、开始状态和结束状态非常容易。

所以，有 5 * 4 * 3 = 60 个状态

您可能会注意到，有一些无法实现的状态和一些可能联合到 "failed states" 的状态可以显着减少自动机的大小

Answer 2

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

让您的状态为 (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, '').

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

计算重叠的 00 和 11。

上面的答案假设'000'包含一个'00'而不是2个'00'（即'00'的数量是字符串中non-overlapping'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 的州外，所有州都在接受。同样，我们将所有 non-accepting 个状态合并为一个状态。

这有 (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 管道输出的结果：

DFA - 设计一个 DFA，它接受超过 {0,1} 的所有字符串，最多包含两个 00 和三个 11 作为子字符串

DFA - design a DFA that accepts all strings over {0,1} that contains at most two 00's and three 11's as substring

algorithm

math

finite-automata

automata

计算重叠的 00 和 11。

正在生成 FSM 图。