我有一个问题，我真的需要能够使用有限自动机作为一个关联容器的键每个密钥实际上应该代表一个等价类的自动机，这样当我搜索时，我会发现一个等价的自动机（如果存在这样的密钥），即使该自动机不是结构上相同的。
当然，最后一个明显的方法是使用线性搜索，对每个选中的键进行等价性测试我希望能做得更好。
我一直在考虑如何强加一个任意但一致的排序，并导出一个有序比较算法。第一个原则涉及自动机表示的字符串集。评估每个自动机可能的第一个标记集，并基于这两个集应用排序。如有必要，继续使用可能的第二个令牌集、第三个令牌集等。天真地这样做的明显问题是，在证明等价性之前，要检查的令牌集数量是无限的。
我一直在考虑一些模糊的想法——首先最小化输入自动机，然后使用某种闭包算法，或者转换回常规语法，一些涉及生成树的想法。我得出的结论是，我需要放弃一套令牌词汇排序，但到目前为止，我得出的最重要的结论是，这不是微不足道的，我可能更善于阅读别人的ELSES解决方案。
我已经从citeserx下载了一篇论文-Total Ordering on Subgroups and Cosets-但是我的抽象代数还不足以知道这是否相关。
我还想到，也许有某种方法可以从自动机中导出散列，但我还没有考虑这么多。
有人能推荐一篇好论文读吗？-或者至少让我知道我下载的是不是一条红鲱鱼？
最佳答案
我相信你可以从最小化自动机得到一个规范形式对于任何两个等价的自动机，它们的最小形式是同构的（我相信这是来自Myhill-Nerode定理）这种同构关系尊重边标签，当然也尊重节点类（开始、接受、不接受）这使得它比无标记图同构更容易。
我认为，如果您从开始状态开始构建最小化自动机的生成树，并按其标签对输出边排序，那么您将得到自动机的规范形式，然后可以对其进行散列。
编辑：非树边也应该考虑在内，但它们也可以按标签的规范顺序排列。
关于algorithm - 使用有限自动机作为容器的键，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1863856/