有限自动机如何在代码中实现？

Question

如何在Python代码中实现dfa或nfa解决这个问题？

有什么好方法在python中做到这一点？他们曾经在现实世界的项目中使用过吗？

Answer 1

表示DFA的直接方式是字典词典.对于每个州,创建一个字典,该字典由字母表中的字母键入,然后是由状态键入的全局字典.例如,维基百科关于DFA的文章中的以下DFA

可以用这样的字典表示:

dfa = {0:{'0':0, '1':1},
       1:{'0':2, '1':0},
       2:{'0':1, '1':2}}

要针对从相关字母表中提取的输入字符串"运行"dfa(在指定初始状态和接受值集合之后),这很简单:

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

您从初始状态开始,逐字逐句地逐字逐句,并在每一步只需查找下一个状态.完成单步执行后,只需检查最终状态是否处于接受状态集中.

例如

>>> accepts(dfa,0,{0},'1011101')
True
>>> accepts(dfa,0,{0},'10111011')
False

对于NFA,您可以在转换字典中存储多组可能的状态而不是单个状态,并使用该random模块从可能状态集中选择下一个状态.