我正在尝试实现一种识别单词的方法。我已经写了下面的代码,并试图按照我的代码在纸上,并执行它一步一步的例子输入,但我找不到原因,为什么我的代码没有做我想让他做的事。有人看到缺陷了吗?我看不见它,我很困惑为什么它不起作用。你知道吗
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号在自我终结,因为自我终结是[3]作为我的对象的例子。。。。你知道吗
这并不是对代码的修复,因为当您使用递归而不是显式堆栈时,这类问题的解决方案更容易可视化(至少对我来说)。正如我在评论中提到的,NFA实际上允许在给定的输入字符上转换到多个状态,尤其是空字符串。所以我修改了输入规范,允许为每个转换指定一个新状态列表。这里,空字符串上的状态0转换为状态1或状态5(可识别
OK
)。状态2可以在k
上转换为状态3或4。你知道吗印刷品:
使用Epsilon变换识别
ab(cd|ef)gh
因此,事实证明,非递归解决方案比必须正确执行回溯要复杂一些(它需要更多的堆栈)。我已经更改了一些变量名,这对我来说更符合逻辑。下面有两个版本。第二种方法对第一种方法进行了修改,只是做了一些细微的修改,以支持空字符串上的转换:
印刷品:
支持空字符串转换的变体
印刷品:
相关问题 更多 >
编程相关推荐