设计DFA(字母'a'和'b'):字符串中'a'的个数必须是3的倍数,且字符串中不包含'aba'
Designing a DFA (alphabet 'a' and 'b') : The number of 'a' in the string must be a multiple of 3, and the string does not contain 'aba'
问题来了:
这是我第一次想到它时的推理思路:
- 这个好像很难
- 为它找到一个正则表达式似乎很棘手,所以我无法按照此路径将正则表达式转换为 DFA
- 所以我决定解决第一部分问题:接受一个字符串,其'a'的个数是3的倍数。这很简单,你只需要3个状态:1,2,3以1为起始状态,如果有输入'a'则进入下一个,如果是'b'则停留在该状态,起始状态也是结束状态。但在本练习中,这 3 个状态实际上是 3 'big' 个状态。那么问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。
我别无选择,只能靠猜测来得出解决方案。这是我想出的(1、2、3 是完成状态,3 是开始状态,如果收到输入 'a',7 和 9 都会变为 1):
我也在这个上使用了 DFA 最小化,发现它已经是最小化了。然而,教科书给出了另一种解决方案:
但我不明白它是如何正确的!我只是想不通:(。我什至不知道我的解决方案是否 100% 正确。请帮助我,非常感谢:)
你的回答似乎是正确的。我没有仔细证明,但逻辑是相当清楚的。此外,我写了一个 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
问题来了:
这是我第一次想到它时的推理思路:
- 这个好像很难
- 为它找到一个正则表达式似乎很棘手,所以我无法按照此路径将正则表达式转换为 DFA
- 所以我决定解决第一部分问题:接受一个字符串,其'a'的个数是3的倍数。这很简单,你只需要3个状态:1,2,3以1为起始状态,如果有输入'a'则进入下一个,如果是'b'则停留在该状态,起始状态也是结束状态。但在本练习中,这 3 个状态实际上是 3 'big' 个状态。那么问题就变成了设计这些“大国”的内部结构以及它们如何相互作用。
我别无选择,只能靠猜测来得出解决方案。这是我想出的(1、2、3 是完成状态,3 是开始状态,如果收到输入 'a',7 和 9 都会变为 1):
但我不明白它是如何正确的!我只是想不通:(。我什至不知道我的解决方案是否 100% 正确。请帮助我,非常感谢:)
你的回答似乎是正确的。我没有仔细证明,但逻辑是相当清楚的。此外,我写了一个 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