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

Question

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

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

原文由 user5899005 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 模块从可能状态集中选择下一个状态。

原文由 John Coleman 发布，翻译遵循 CC BY-SA 3.0 许可协议