传入列表时，对 epsilon 闭包字典的递归停止工作

Question

我目前正在python中为epsilon闭包创建一个函数。我正在使用递归来运行使用epsilon的NFA中的每个可能的转换。我对该函数的输入是一个格式为

：

tf2 = {('q0','a') : 'q1', ('q1','eps') : ['q2', 'q3'], ('q3','eps') : 'q0', ('q2','a') : 'q4', ('q4','eps') : 'q3'}

其中键是 2 元组(当前状态、输入(，值是结果状态。

在这种情况下，我尝试关闭的转换是'eps'是键的第二部分的转换。

我遇到的问题是，每当传入包含列表的值时(如在('q1','eps') : ['q2', 'q3']条目中(，我的递归都会失败，并出现"unhashable type: 'list'"异常。

我现在的代码如下：

tf2 = {('q0','a') : 'q1', ('q1','eps') : ['q2', 'q3'], ('q3','eps') : 'q0', ('q2','a') : 'q4', ('q4','eps') : 'q3'}
def epsilonClosure(transition, state):
    closure = []
    if (state, 'eps') not in transition:    # epsilon transition not possible
        return closure
    elif (state, 'eps') in transition:    # epsilon transition is possible
        closure.append(state)
        state = transition[(state, 'eps')]
        epsilonClosure(transition, state)
    if state not in closure:    # adds current state to list if not visited before
        closure.append(state)
    return closure
epsilonClosure(tf2, 'q1')

此代码适用于字典中的非列表值，但在命中列表时中断。

任何帮助将不胜感激，谢谢！

-编辑修复了代码，因此它在隔离时是可执行的。不好意思！

Answer 1

让我们暂时忽略错误，并从问题的角度思考。您的函数需要一个状态的名称作为变量 state 的值。但是，列表['q2', 'q3']不是有效的状态。相反，每个字符串'q2'和'q3'都是。您需要修改算法以考虑到这一点。我可以想到两个选项：

1. 更改参数列表以接受状态列表。然后循环访问此列表。

2. 更改递归调用以调用列表中每个状态的函数。

如果您可以控制字典输入，我建议您使用列表作为所有值。您可以在需要时轻松制作一个包含一种状态的列表。这将允许您编写算法以始终处理状态名称列表。

如果无法执行此操作，则首先必须检查字典中的值是否为列表，并将其与字符串区别对待。