2

我正在和学生一起创建一个有限状态机的简单演示：

s2 = {}
s1 = {}
s1["0"] = s2
s1["1"] = s1
s2["0"] = s1
s2["1"] = s2
machine = {"start": s1, "accepting": [s1]}

def recognize(fsm, in_string):
    return do_recognize(fsm, fsm["start"], in_string)

def do_recognize(fsm, current, in_string):
    if len(in_string) == 0:
        return current in fsm["accepting"]

   return do_recognize(fsm, current[in_string[0]] ,
                 in_string[1:])

print (recognize(machine, "0"))

这台机器可以识别偶数个 0 的字符串，并且它可以很好地处理“好”字符串（例如“1”或“010”）。但是在上面这样的“坏”字符串上，它会进入无限循环，然后在 fsm[“accepting”] 中的返回电流处堆栈溢出。

我能够确定问题在于两种状态的比较。事实上，我可以通过编写 s1 == s2 来生成完全相同的错误。但是 s1 == s1 （一个好的状态）工作正常。

我对正在发生的事情的最佳猜测是，它正在进行深度比较并试图遵循 s2 中的所有引用，这些引用是循环的。但为什么它是不对称的（即为什么 s1 == s1 没有同样的问题）？我该如何避免呢？

4

2 回答 2

4

问题与s1和之间的循环引用有关s2。

这使得无法进行比较s1（s2就目前cmp()而言，这两个字典具有无限的深度）。考虑以下：

print s1 == s1 # immediately returns True, probably due to equal object ids
print s1 == s2 # RuntimeError: maximum recursion depth exceeded in cmp

这解释了为什么s1 in fsm["accepting"]工作和s2 in fsm["accepting"]休息。

解决此问题的一种简单方法是更换

return current in fsm["accepting"]

和

return id(current) in map(id, fsm["accepting"])

这会按身份比较状态，而不是尝试按值比较两个无限深的字典。

于 2012-11-28T16:35:18.687 回答
2

比较字典时，还会比较字典中的每个项目（键/值对），因此如果在循环引用涉及相同键的字典之间存在循环引用，则在比较它们时会出现此最大递归深度超出错误：

例如，如果您有s1 == {'0': s2}and s2 == {'0': s1}，那么尝试s1 == s2将导致以下比较，这说明了递归是如何发生的：

s1 == s2 --> s1['0'] == s2['0'] --> s2 == s1 --> s2['0'] == s1['0'] --> s1 == s2 --> ...

类似s1 in [s2]or的包含测试s2 in [s1]也会导致这种相等比较，这就是它发生在您的代码中的原因current in fsm["accepting"]。

您可以通过使用身份比较而不是相等比较来解决此递归问题，只需替换current in fsm["accepting"]为以下内容：

any(s is current for s in fsm["accepting"])

A better solution might be to not use circular references by having the states refer to an identifier instead of the object itself, for example you could have a structure like the following:

states = {"s1": {"0": "s2", "1": "s1"},
          "s2": {"0": "s1", "1": "s2"}}
machine = {"start": "s1", "accepting": ["s1"]}

def recognize(fsm, in_string):
    return do_recognize(fsm, fsm["start"], in_string)

def do_recognize(fsm, current, in_string):
    if len(in_string) == 0:
        return current in fsm["accepting"]
    return do_recognize(fsm, states[current][in_string[0]], in_string[1:])
于 2012-11-28T16:49:47.887 回答