<p>在这里,我给出了NFA的递归解决方案。</p>
<p>考虑以下nfa:</p>
<p><a href="https://i.stack.imgur.com/3gyq3.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3gyq3.png" alt="enter image description here"/></a></p>
<p>可以使用列表列表来表示转换,如下所示:</p>
<p>转换=<code>[[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]</code></p>
<p><strong>注意:</strong>状态4是一个假设状态。一旦你去了那个州,你就不能再往前走了。当您无法从当前状态读取输入时,它会很有帮助。直接进入状态4,并说当前进度不接受输入(通过返回检查其他可能性)。e、 g,如果您在<code>q1</code>,并且当前的输入符号是<code>'a'</code>,则转到状态4并进一步停止计算。</p>
<p>下面是Python代码:</p>
<pre><code>#nfa simulation for (a|b)*abb
#state 4 is a trap state
import sys
def main():
transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]]
input = raw_input("enter the string: ")
input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly
for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity
if input[index]=='a':
input[index]='0'
else:
input[index]='1'
final = "3" #set of final states = {3}
start = 0
i=0 #counter to remember the number of symbols read
trans(transition, input, final, start, i)
print "rejected"
def trans(transition, input, final, state, i):
for j in range (len(input)):
for each in transition[state][int(input[j])]: #check for each possibility
if each < 4: #move further only if you are at non-hypothetical state
state = each
if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states
print "accepted"
sys.exit()
trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:]
i = i+1 #increment the counter
main()
</code></pre>
<p><strong>样本输出:</strong>(接受以abb结尾的字符串)</p>
<pre><code>enter the string: abb
accepted
enter the string: aaaabbbb
rejected
</code></pre>
<p>。。。。。。</p>