使用有限自动机作为容器的键 [英] Using finite automata as keys to a container

问题描述

我有一个问题，我真的需要能够使用有限自动机作为关联容器的键。每个键实际上应该代表一个等效的自动机类，因此，当我搜索时，即使该自动机在结构上不相同，我也会找到一个等效的自动机（如果存在这样的键）。

I have a problem where I really need to be able to use finite automata as the keys to an associative container. Each key should actually represent an equivalence class of automata, so that when I search, I will find an equivalent automaton (if such a key exists), even if that automaton isn't structurally identical.

一个显而易见的最后解决方法当然是对每个检查的键使用线性搜索和等效测试。我希望有可能做得比这更好。

An obvious last-resort approach is of course to use linear search with an equivalence test for each key checked. I'm hoping it's possible to do a lot better than this.

我一直在尝试施加任意但一致的顺序，并得出有序的顺序比较算法。第一原则涉及自动机代表的字符串集。为每个自动机评估可能的第一个标记的集合，并基于这两个集合应用排序。如有必要，请继续使用可能的第二个令牌，第三个令牌等的集合。天真地这样做的一个明显问题是，在证明等价性之前，要检查的令牌集合数量是无限的。

I've been thinking in terms of trying to impose an arbitrary but consistent ordering, and deriving an ordered comparison algorithm. First principles involve the sets of strings that the automata represent. Evaluate the set of possible first tokens for each automaton, and apply an ordering based on those two sets. If necessary, continue to the sets of possible second tokens, third tokens etc. The obvious problem with doing this naively is that there's an infinite number of token-sets to check before you can prove equivalence.

我一直在考虑一些模糊的想法-首先最小化输入自动机并使用某种闭包算法，或者转换回常规语法，其中一些想法涉及生成树。我得出的结论是，我需要放弃令牌集的词法排序，但是到目前为止，我得出的最重要的结论是，这并非微不足道，我最好还是继续读下去。

I've been considering a few vague ideas - minimising the input automata first and using some kind of closure algorithm, or converting back to a regular grammar, some ideas involving spanning trees. I've come to the conclusion that I need to abandon the set-of-tokens lexical ordering, but the most significant conclusion I've reached so far is that this isn't trivial, and I'm probably better off reading up on someone elses solution.

我已经从CiteSeerX下载了一篇论文-子组和陪集的总排序-但是我的抽象代数甚至还不足以知道这是否有意义。

I've downloaded a paper from CiteSeerX - Total Ordering on Subgroups and Cosets - but my abstract algebra isn't even good enough to know if this is relevant yet.

我还想到可能有某种方法可以从自动机中获取哈希值，但是我还没有考虑太多。

It also occurred to me that there might be some way to derive a hash from an automaton, but I haven't given this much thought yet.

有人能推荐一篇好论文来阅读吗？ -或至少让我知道我下载的是不是鲱鱼？

Can anyone suggest a good paper to read? - or at least let me know if the one I've downloaded is a red herring or not?

推荐答案

我相信您可以从最小化的自动机获得规范形式。对于任何两个等效的自动机，它们的最小化形式是同构的（我相信这来自Myhill-Nerode定理）。这种同构关系涉及边缘标签，当然也涉及节点类（开始，接受，不接受）。

I believe that you can obtain a canonical form from minimized automata. For any two equivalent automatons, their minimized forms are isomorphic (I believe this follows from Myhill-Nerode theorem). This isomorphism respects edge labels and of course node classes (start, accepting, non-accepting). This makes it easier than unlabeled graph isomorphism.

我认为，如果您从起始状态开始构建最小化自动机的生成树，并按其标签对输出边进行排序，那么您将获得自动机的规范形式，然后可以对其进行哈希处理。

I think that if you build a spanning tree of the minimized automaton starting from the start state and ordering output edges by their labels, then you'll get a canonical form for the automaton which can then be hashed.

编辑：也应考虑非树的边缘，但也可以通过其标签规范地对其进行排序。

Non-tree edges should be taken into account too, but they can also be ordered canonically by their labels.

这篇关于使用有限自动机作为容器的键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！