如何在代码中实现有限自动机? [英] How are finite automata implemented in code?

问题描述

如何在Python代码中为此实现dfa或nfa?

How does one implement a dfa or an nfa for that matter in Python code?

在python中有哪些好的方法? 他们曾经在现实世界的项目中使用过吗?

What are some good ways to do it in python? And are they ever used in real world projects?

推荐答案

表示DFA的直接方法是将其作为词典的字典.对于每个州，创建一个由字母字母作为键的字典，然后创建一个由州作为键的全局字典.例如，以下有关DFA的维基百科文章

A straightforward way to represent a DFA is as a dictionary of dictionaries. For each state create a dictionary which is keyed by the letters of the alphabet and then a global dictionary which is keyed by the states. For example, the following DFA from the Wikipedia article on DFAs

可以用这样的字典表示:

can be represented by a dictionary like this:

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

要对从有问题的字母表中提取的输入字符串运行" dfa(在指定了初始状态和一组接受值之后)很简单:

To "run" a dfa against an input string drawn from the alphabet in question (after specifying the initial state and the set of accepting values) is straightforward:

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

您从初始状态开始，逐个字符地逐步操作字符串，然后在每个步骤中仅查找下一个状态.完成字符串的遍历后，您只需检查最终状态是否在接受状态集中即可.

You start in the initial state, step through the string character by character, and at each step simply look up the next state. When you are done stepping through the string you simply check if the final state is in the set of accepting states.

例如

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

对于NFA，您可以在过渡字典中存储可能的状态集而不是单个状态，并使用random模块从可能的状态集中选择下一个状态.

For NFAs you could store sets of possible states rather than individual states in the transition dictionaries and use the random module to pick the next state from the set of possible states.

这篇关于如何在代码中实现有限自动机?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！