在递归函数调用中收集乘法 return 值（自动机 nfa 处理）

Question

我正在编写一个 NFA（非确定性有限自动机）class，它应该解析给定的输入并 returns 所有可能的轨迹（从初始状态到最终状态的路径）。最终，我想计算给定自动机的模糊度。

不幸的是，我无法正确收集方法的 return。此版本的代码 returns None 和使用 yield returns 稍作修改的代码仅第一个，路径。

这个问题好像有点含糊，希望有人能给我指点一下。

提前致谢。

class NFA(object):
    __slots__ = [
        'states',
        'alphabet',
        'transitions',
        'initial_state',
        'final_states',
    ]

    #
    #
    #  -------- Init -----------
    #
    def __init__(
            self,
            states: set,
            alphabet: set,
            transitions: dict,
            initial_state: str,
            final_states: set,
    ):
        """
            Initialize a complete automaton.
        """

        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.initial_state = initial_state
        self.final_states = final_states

    #
    #
    #  -------- process -----------
    #
    def process(self, word: str, trace: list = []) -> list:
        """
        Check if the given string is accepted by this automaton.
        Return all accepting paths.
        """

        # processing finished returning the trace
        if (not word):
            print(trace)
            return trace

        # start processing with initial state
        if (not trace):
            trace.append(self.initial_state)

        # get the current state transitions
        state_transition: dict = self.transitions.get(trace[-1], None)

        # input not accepted
        if (not state_transition):
            return False

        # iterate over each possible transition
        for state in state_transition.get(word[0], []):

            # create new sub trace, append current state
            sub_trace: list = trace.copy()
            sub_trace.append(state)

            # start recursive function call
            self.process(word[1:], trace=sub_trace)

from automata.nfa import NFA

config: dict = {
    'states': ['q0', 'q1', 'q2'],
    'alphabet': ['a'],
    'transitions': {
        'q0': {
            'a': ['q1', 'q2']
        },
        'q1': {
            'a': ['q1']
        }
    },
    'initial_state': 'q0',
    'final_states': ['q1'],
}

testNFA = NFA(**config)

assert testNFA.process("a") == [['q0', 'q1'], ['q0', 'q2']]

Answer 1

听起来您基本上是在要求基本的 DFS。我认为这种设计混淆了一些东西。

如果你 return 来自递归调用的东西，数据只会返回到它的直接调用者，并且需要一直沿着调用链返回到原始范围。如果您不想使用生成器，您可能需要某种主结果列表参数，当您遇到 word 已被消耗且NFA处于接受状态。内部函数对此很有用，可以避免向调用者公开大量默认参数。

一种可能更好的方法是使用 generator，它避免处理管理结果列表和传递 return 值，并让调用者控制如何使用结果。

你提到你尝试了一个生成器版本，但是递归生成器use a yield from要应用于递归调用。

考虑到这种方法，您显示的代码没有考虑 final_states，因此根据“从初始状态到最终状态的路径”的问题描述，您的预期输出似乎不正确。我预计 [['q0', 'q1']] 是所需的输出，因为 "q2" 不是接受状态。但是，正如您在下面的代码片段中看到的那样，在两者之间做出决定是微不足道的。

作为实现细节，每次递归调用对字符串进行切片是 O(n)。您可以使用索引在所有递归调用框架共享的单个字符串中跟踪您的位置，以避免这种成本。类似地，在每次调用时复制 trace 列表比将一个列表保存到 push/pop 并且仅在 yield.

上复制它要慢

注意 mutable default argument.

这是一个最小的完整示例：

from collections import namedtuple

def find_accepting_paths(nfa, word, trace=None):
    trace = trace if trace else [nfa.initial_state]

    if word:
        for state in nfa.transitions.get(trace[-1], {}).get(word[0], []):
            trace.append(state)
            yield from find_accepting_paths(nfa, word[1:], trace)
            trace.pop()
    elif trace[-1] in nfa.final_states: # or use `else` if you're sure you
                                        # don't care about accepting states
        yield trace[:]

if __name__ == "__main__":
    NFA = namedtuple("NFA", "transitions initial_state final_states")
    nfa = NFA(
        transitions={
            "q0": {
                "a": ["q1", "q2"]
            },
            "q1": {
                "a": ["q1"]
            }
        },
        initial_state="q0",
        final_states=["q1"],
    )
    print(list(find_accepting_paths(nfa, "a"))) # => [['q0', 'q1']]

在递归函数调用中收集乘法 return 值（自动机 nfa 处理）

Collecting multiply return values in a recursive function call (automaton nfa processing)

python

recursion

automaton