4

这是问题所在： 在此处输入图像描述

这是我第一次遇到它时的推理路线：

  • 这个好像很难
  • 为其查找正则表达式似乎很棘手，因此我无法按照此路径将正则表达式转换为 DFA
  • 所以我决定解决问题的第一部分：接受一个“a”个数是 3 的倍数的字符串。这很简单，你只需要 3 个状态：1、2、3，以 1 为起始状态，如果有输入'a'，则进入下一个，如果是'b'，则停留在该状态，并且开始状态也是完成状态。但在本练习中，这 3 个州实际上是 3 个“大”州。然后问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。

我别无选择，只能使用猜测来得出解决方案。这是我想出的（1,2,3 是完成状态，3 是开始状态，如果收到输入“a”，7 和 9 都变为 1）： 在此处输入图像描述 我还使用了 DFA 最小化，并发现它已经很小了。但是，教科书给出了另一种解决方案： 在此处输入图像描述

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

4

1 回答 1

2

你的答案似乎是正确的。我没有仔细证明，但逻辑相当清楚。此外，我编写了一个 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中解释了该功能的操作。我对其进行了定制以匹配您的图表。为了对其进行压力测试，我生成了 100,000 个长度范围从 1 到 1000 的随机输入，然后将 DFA 的输出与条件的直接验证进行了比较。每次我运行这段代码时，输​​出都是令人满意的.True

要测试单个字符串：

>>> dfaTest('ababba')
False
>>> dfaTest('abbabba')
True
于 2017-01-01T15:25:23.863 回答