使用有限自动机作为容器的键

我认为,如果你从开始状态开始构建最小化自动机的生成树,并根据它们的标签对输出边进行排序,那么你将得到自动机的规范形式,然后可以对其进行散列。

编辑:非树边也应该考虑在内,但它们也可以按标签进行规范排序。

Minimization of Nondeterministic Finite Automata

一旦拥有了规范表单,您就可以轻松地对其进行散列,例如,通过对状态和转换执行深度优先枚举,并对通过对状态编号进行编码(按其第一次出现的顺序进行计数)获得的字符串进行散列,将状态和转换作为三元组

<from_state, symbol, to_state, is_accepting_final_state>

正如在这个问题中提出的,为了词汇化这两个自动机,我需要考虑两件事。两组可能的第一个标记,以及两组可能的其他所有标记。尾部可以表示为有限自动机,并且可以从原始自动机派生。

因此,比较算法是递归的——比较头部,如果结果不同,则递归比较尾部。

问题在于证明正则文法等价性所需的无限序列。如果在比较过程中,一对自动机重复出现,相当于您之前检查过的一对自动机,那么您已经证明了等价性,可以停止检查。这是在有限自动机的性质,这必须发生在有限数量的步骤。

这也证明了那篇论文是相关的,但可能只带我走了这么远。正则语言可以使用连接操作符形成一个组,左陪集与我一直在考虑的head:tail相关。

我之所以是个白痴是因为我强加了一个过于严格的终止条件,我应该知道这一点,因为WRT自动机算法的问题并不罕见。

当然,仍然存在性能问题。基于这里涉及的问题,使用标准等价算法的线性搜索可能是一种更快的方法。当然,我希望这种比较比现有算法的等价性测试效率更低,因为它做的工作更多——对非等价情况进行词汇排序。真正的问题是基于关键字的搜索的总体效率,这可能需要一些令人头痛的分析。我希望,非等价自动机将倾向于快速比较(在前几个步骤中检测差异,就像传统的字符串比较一样),这一事实将使这成为一种实用的方法。

如果您所能做的就是==或!=,然后,我认为在添加另一个集合成员之前,必须检查每个集合成员。这太慢了(编辑:考虑到问题的标题,我想你已经知道了这一点,即使你继续讨论比较函数来直接比较两个有限自动机。)