python - 我正在尝试在 Python 中实现 NFA 来识别单词，但我的代码不起作用，

Question

我正在尝试实现一种识别单词的方法。我编写了以下代码，并尝试遵循纸上的代码并使用示例输入逐步执行它，但我找不到我的代码没有执行我希望他执行的操作的原因。有人看到缺陷吗？我看不到它，我很困惑为什么它不起作用。

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....

Answer 1

这并不是对代码的完全修复，因为当您使用递归而不是显式堆栈时，此类问题的解决方案更容易可视化(至少对我来说)。正如我在评论中提到的，NFA 实际上允许在给定输入字符上转换到多个状态，包括特别是空字符串。因此，我修改了输入规范，以允许为每个转换指定新状态列表。这里，状态 0 在空字符串上转换为状态 1 或状态 5(识别 OK)。状态 2 可以在 k 上转换到状态 3 或 4。

from collections import defaultdict

class NFA:
    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)
            for state in tgt:
                self.trns[src, char].add(state)

    def recognize_next_char(self, state, strng, index):
        ch = '' if state in self.epsilon_states else strng[index]
        if (state, ch) in self.trns.keys():
            next_states = self.trns[(state, ch)]
            if ch != '':
                index += 1
            for next_state in next_states:
                if index == len(strng):
                    if next_state in self.final:
                        return True
                elif self.recognize_next_char(next_state, strng, index):
                    return True
            return False
        else:
            return False

    def recognizewords(self, strng):
        if len(strng) == 0:
            if self.initial in self.final:
                return True
            if self.initial not in self.epsilon_states:
                return false
        return self.recognize_next_char(self.initial, strng, 0)

exampleO = NFA(0, [(0,'',(1,5)), (1,'o',(2,)), (2,'k',(3,4)), (3,'i',(2,)), (4,'!',(99,)), (5,'O', (6,)), (6,'K',(99,))], [99])
print(exampleO.recognizewords("okikik!"))
print(exampleO.recognizewords("ok!"))
print(exampleO.recognizewords("OK"))
print(exampleO.recognizewords("ok"))
print(exampleO.recognizewords("oki"))
print(exampleO.recognizewords("okx"))

打印:

True
True
True
False
False
False

使用 Epsilon 转换识别 ab(cd|ef)gh 的示例