我正在尝试在Python中实现NFA以识别单词,但是我的代码无法正常工作, [英] I am trying to implement NFA in Python to recognize words but my code doesn't work,
问题描述
我正在尝试实现一种识别单词的方法.我编写了以下代码,并尝试在纸上遵循我的代码,并使用示例输入逐步执行它,但是我找不到我的代码没有按我希望他做的那样的原因.有人看到这个缺陷吗?我看不到它,我对为什么它不起作用感到困惑.
I am trying to implement a method that recognizes words. I have written the following code and have tried to follow my code on paper and execute it step by step with example inputs, but I can't find the reason why my code is not doing what I want him to do. Does anyone see the flaw? I can't see it and I am confused on why it doesn't work.
from collections import defaultdict
class NFA:
def __init__(self, initial, trns, final):
self.initial = initial
self.final = set(final)
self.trns = defaultdict(set)
for (src, char, tgt) in trns:
self.trns[src, char].add(tgt)
def recognizewords(self, strng):
strang = [char for char in strng]
strang.reverse()
visited = set()
agenda = [self.initial]
while strang and agenda:
currentletter = strang.pop()
current = agenda.pop()
visited.add(current)
if (current, currentletter) in self.trns.keys():
state = self.trns[(current, currentletter)]
for st in state:
if strang == [] and state in self.final:
return True
for i in self.trns[(current, currentletter)]:
agenda.append(i)
return False
exampleO = NFA(0, [(0,'o',1), (1,'k',2), (2,'i',1), (2,'!',3)], [3])
print(exampleO.recognizewords("ok!"))
它应该返回True,因为在某一时刻我的列表"strang"将为空(当我将currentletter分配给!"时),同时3在self.final中,因为self.final为[3]对于我的对象示例O ....
It should return True, because at one point my list "strang" will be empty (when I assigned currentletter to "!") and at the same time 3 is in self.final, because self.final is [3] for my object exampleO....
推荐答案
因此,事实证明,非递归解决方案比正确执行回溯要复杂得多(它需要更多堆栈).我更改了一些变量名,对我而言,这更合逻辑.下面有两个版本.第二个修改了第一个,仅作了一些细微的更改以支持对空字符串的过渡:
So as it turns out that the non-recursive solution is a bit more complicated than what you had to do backtracking correctly (it requires more stacks). I have changed a few variable names, which for me are more logical. There are two versions below. The second one modifeds the first with just a few slight changes to support transitions on empty strings:
from collections import defaultdict
class NFA:
def __init__(self, initial, trns, final):
self.initial = initial
self.final = set(final)
self.trns = defaultdict(set)
for (src, char, tgt) in trns:
self.trns[src, char].add(tgt)
def recognizewords(self, strng):
strlen = len(strng)
if strlen == 0:
return self.initial in self.final
index = 0
next_states = [self.initial]
next_states_stack = []
index_stack = []
while index < strlen:
current_letter = strng[index]
if next_states:
state = next_states.pop()
if (state, current_letter) in self.trns.keys():
new_next_states = self.trns[(state, current_letter)]
if new_next_states & self.final:
# did we use up all the characters?
return index == strlen - 1
next_states_stack.append(next_states)
index_stack.append(index)
next_states = list(new_next_states)
index += 1
elif next_states_stack:
next_states = next_states_stack.pop()
index = index_stack.pop()
else:
return False
return False
# ab(d|e)
exampleO = NFA(0, [(0,'a',1), (1,'b',2), (1,'b',3), (2,'d',4), (3,'e',4)], [4])
print(exampleO.recognizewords("abd"))
print(exampleO.recognizewords("abe"))
打印:
True
True
支持在空字符串上进行过渡的变体
from collections import defaultdict
class NFA_Epsilon:
def __init__(self, initial, trns, final):
self.initial = initial
self.final = set(final)
self.trns = defaultdict(set)
self.epsilon_states = set()
for (src, char, tgt) in trns:
if char == '':
self.epsilon_states.add(src)
self.trns[src, char].add(tgt)
def recognizewords(self, strng):
strlen = len(strng)
if strlen == 0:
return self.initial in self.final
index = 0
next_states = [self.initial]
next_states_stack = []
index_stack = []
while index < strlen:
if next_states:
state = next_states.pop()
current_letter = '' if state in self.epsilon_states else strng[index]
if (state, current_letter) in self.trns.keys():
new_next_states = self.trns[(state, current_letter)]
if new_next_states & self.final:
# did we use up all the characters?
return index == strlen - 1
next_states_stack.append(next_states)
index_stack.append(index)
next_states = list(new_next_states)
if current_letter != '':
index += 1
elif next_states_stack:
next_states = next_states_stack.pop()
index = index_stack.pop()
else:
return False
return False
# ab(cd|ef)gh
example1 = NFA_Epsilon(0, [
(0,'a',1),
(1,'b',2),
(2,'',3),
(2,'',6),
(3,'c',4),
(4,'d',5),
(5,'',9),
(6,'e',7),
(7,'f',8),
(8,'',9),
(9,'g',10),
(10,'h',11)
],[11])
print(example1.recognizewords('abcdgh'))
print(example1.recognizewords('abefgh'))
打印:
True
True
这篇关于我正在尝试在Python中实现NFA以识别单词,但是我的代码无法正常工作,的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!