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}}
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.
For example
>>> accepts(dfa,0,{0},'1011101')
True
>>> accepts(dfa,0,{0},'10111011')
False
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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…