python中DFA的设计与实现
python中DFA的设计与实现
提问于 2017-02-12 20:58:26
我有一种语言L，它简单地由字符串组成，这些字符串是URL，我需要设计和实现一个识别L的DFA (例如: www.test.com)。我现在的问题是，一旦你把所有的东西都读到‘www’，你怎么知道什么时候停止读".com"？
到目前为止我的代码是：
s = input("Would you like to input a string? y/n")
if(s == 'n'):
exit
dfa = {'':{'w':'ww'}, 'w': {'w': 'ww'}, 'ww': {'w': 'www'},'www': {'.': 'www.'},"}}
def accepts(transitions,initial,accepting,s):
state = initial
for c in s:
state = transitions[state][c]
return state in accepting
accepts(dfa,0,{0},"www.hi.com")任何帮助都是非常感谢的！(请注意，我暂时从here借用了一个函数，这样我就可以理解起作用的概念了。
回答 2
Stack Overflow用户
回答已采纳
发布于 2017-02-12 21:11:37
DFA基本上是由transition table定义的。此转换表将当前状态和当前输入的每个(有效)组合映射到相应的后续状态。这样的一张表可以模拟成字典。例如:外部字典包含作为键的状态和作为值的字典，这些字典依次以有效的输入作为键，而后续的状态作为值。
编辑:您选择的示例并不理想，因为它有相当大的字母表(即所有可能的输入字符)至少是[a-zA-Z0-9]，链接的答案只限于[01]，原因是-)我从没有少说：
{
# in state '' we have not yet processed/consumed any input
# it is the start state
# the only valid input is a 'w'
'': {'w': 'w'},
# in state 'w' we a have already consumed a 'w'
# the only valid input is another 'w'
'w': {'w': 'ww'},
# in state 'ww' we have previously consumed 'ww'
# the only valid input is still only a 'w'
'ww': {'w': 'www'},
# now the only valid input is a '.'
'www': {'.': 'www.'},
# this is where your example becomes unpractical:
# we have to add a transition for every valid input
# (you could get around this by using a defaultdict and some kind of special signal value, but im not quite sure you are up to that)
'www.': {'a': 'www.*', 'b': 'www.*', ...},
# I used the star in this state name to symbolize multiple (at least one) valid character
# we only leave this state if we encounter a '.'
'www.*': {'.': 'www.*.', 'a': 'www.*', 'b': 'www.*', ...},
# it should be obvious how to continue from here
'www.*.': ...
}EDIT2:聊天后的实现。
from collections import defaultdict
dfa = {
'initial': defaultdict(lambda: 'invalid', w='w'),
'w': defaultdict(lambda: 'invalid', w='ww'),
'ww': defaultdict(lambda: 'invalid', w='www'),
'www': defaultdict(lambda: 'invalid', [('.','www.')]),
'www.': defaultdict(lambda: 'www.*', [('.','invalid')]),
'www.*': defaultdict(lambda: 'www.*', [('.','www.*.')]),
'www.*.': defaultdict(lambda: 'www.*', [('c','www.*.c')]),
'www.*.c': defaultdict(lambda: 'www.*', [('o','www.*.co')]),
'www.*.co': defaultdict(lambda: 'www.*', [('m','www.*.com'), ('.','www.*.')]),
'www.*.com': defaultdict(lambda: 'www.*', [('.','www.*.')]),
'invalid': defaultdict(lambda: 'invalid')
}
def accepts(transitions,initial,accepting,s):
state = initial
for c in s:
state = transitions[state][c]
print(c, '->', state)
return state in accepting
print(accepts(dfa,'initial',{'www.*.com', 'www.*.co'},"www.hi.com"))Stack Overflow用户
发布于 2017-02-12 21:12:15
有一个答案here解释了这是如何实现的，但您也会问为什么字典字典可以解释不同的状态。因此，从上面提到的答案来看，让我们以下面的例子为例：
dfa = {0:{'0':0, '1':1},
1:{'0':2, '1':0},
2:{'0':1, '1':2}}如您所见，第一个字典包含数字0、1和2，它们是字典本身。这是你们的州。在他们的字典里有一个字符，你的dfa会读的，'0'或'1'。对于这些读字符，它也会给你下一个状态。
例如：
- 你从状态0开始
- 你读字符'1‘
- 你进入第一州
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42193173
复制相关文章
相似问题
腾讯云开发者
