我正在练习我的 DFA,我遇到了这个似乎非常复杂的问题。我试着把它分成两个较小的问题,我有一个答案,但它看起来不适合我。
有人可以帮助我,或者至少给我一些提示。
我能想到的另一种可能性是,你只有每两个 O 或 1 的接受状态,因为它们需要成对。因此,例如 11 接受 11 接受 11 接受。
最佳答案
您将您的状态机描述为一幅巨大的图画,但您可以通过使用结构化名称命名您的状态来简化您的问题,而不是试图绘制一张巨大的图表。
让你的状态为 (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 '}'
关于algorithm - DFA - 设计一个 DFA 接受超过 {0,1} 的所有字符串,最多包含两个 0 0's and three 11' 作为子字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34710885/