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

Question

如何在 Python 代码中实现 DFA 或 NFA？

在 Python 中有哪些好的方法可以做到这一点？它们曾用于现实世界的项目中吗？

Answer 1

表示 DFA 的一种直接方法是作为字典的字典。为每个状态创建一个由字母表中的字母键入的字典，然后创建一个由状态键入的全局字典。例如，来自 Wikipedia article on DFAs 的以下 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 模块从可能状态集中选择下一个状态。