在 python 中设计和实施 DFA
designing and implementing a DFA in python
我有一种语言 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 借用了一个函数,以便我可以理解其中的概念。
DFA 基本上由 transition table
定义。此转换 table 将当前状态和当前输入的每个(有效)组合映射到相应的后继状态。这样的 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"))
有一个答案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”
- 你进入状态 1
我有一种语言 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 借用了一个函数,以便我可以理解其中的概念。
DFA 基本上由 transition table
定义。此转换 table 将当前状态和当前输入的每个(有效)组合映射到相应的后继状态。这样的 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"))
有一个答案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”
- 你进入状态 1