finite-automata - 设计一个 DFA(字母 'a' 和 'b'): The number of 'a' in the string must be a multiple of 3, 并且字符串不包含 'aba'

Question

这是问题所在:


这是我第一次遇到它时的推理思路:

这个好像很难

为其查找正则表达式似乎很棘手，因此我无法按照此路径将正则表达式转换为 DFA

所以我决定解决问题的第一部分:接受一个'a'的数量是3的倍数的字符串。这很容易，你只需要3个状态:1、2、3，以1作为起始状态，如果有一个输入'a'，你就去下一个，如果是'b'你就停留在那个状态，开始状态也是结束状态。但在本练习中，这 3 个州实际上是 3 个“大”州。然后问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。

我别无选择，只能通过猜测来找到解决方案。这是我想出的(1,2,3 是结束状态，3 是开始状态，如果接收到输入'a'，7 和 9 都会变为 1):

我也在这个上使用了 DFA 最小化，发现它已经是最小的。但是，教科书给出了另一种解决方案:


但我不明白它是如何正确的!我就是想不通:(。我什至不知道我的解决方案是否 100% 正确。请帮助我，非常感谢 :)

Answer 1

你的答案似乎是正确的。我没有仔细证明它，但逻辑相当清楚。此外，我编写了一个 Python 程序来测试它:

def accepts(transitions,initial,accepting,s):
    state = initial
    for c in s:
        state = transitions[state][c]
    return state in accepting

dfa = {1:{'a':4, 'b':2},
       2:{'a':10, 'b':3},
       3:{'a':4, 'b':3},
       4:{'a':7, 'b':5},
       5:{'a':10, 'b':6},
       6:{'a':7, 'b':6},
       7:{'a':1, 'b':8},
       8:{'a':10, 'b':9},
       9:{'a':1, 'b':9},
       10:{'a':10, 'b':10}}

def dfaTest(s):
    return accepts(dfa,3,{1,2,3},s)

def valid(s):
    return s.count('a') % 3 == 0 and not 'aba' in s

import random

tests = [''.join(random.choice(['a','b']) for j in range(100)) for i in range(1,1001)]

print(all(valid(s) == dfaTest(s) for s in tests))

函数的操作accepts解释在 this answer .我量身定制了它以匹配您的图表。为了对其进行压力测试，我生成了 100,000 个随机输入，其长度范围从 1 到 1000，然后将 DFA 的输出与条件的直接验证进行比较。每次运行这段代码，输出都是令人满意的 True .

测试单个字符串:

>>> dfaTest('ababba')
False
>>> dfaTest('abbabba')
True