擅长:python、mysql、java
<p>表示DFA的一种简单方法是使用字典。为每个州创建一个由字母表的字母键控的字典,然后创建一个由州键控的全局字典。例如,来自<a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton" rel="noreferrer">Wikipedia article on DFAs</a>的以下DFA</p>
<p><a href="https://i.stack.imgur.com/s7uO2.png" rel="noreferrer"><img src="https://i.stack.imgur.com/s7uO2.png" alt="enter image description here"/></a></p>
<p>可以用这样的字典来表示:</p>
<pre><code>dfa = {0:{'0':0, '1':1},
1:{'0':2, '1':0},
2:{'0':1, '1':2}}
</code></pre>
<p>对从所讨论的字母表中提取的输入字符串“运行”dfa(在指定初始状态和接受值集之后)很简单:</p>
<pre><code>def accepts(transitions,initial,accepting,s):
state = initial
for c in s:
state = transitions[state][c]
return state in accepting
</code></pre>
<p>您从初始状态开始,一个字符一个字符地遍历字符串,在每个步骤中只需查找下一个状态。单步执行完字符串后,只需检查最终状态是否在接受状态集中。</p>
<p>例如</p>
<pre><code>>>> accepts(dfa,0,{0},'1011101')
True
>>> accepts(dfa,0,{0},'10111011')
False
</code></pre>
<p>对于NFAs,您可以在转换字典中存储可能的状态集,而不是单个状态,并使用<code>random</code>模块从可能的状态集中选择下一个状态。</p>