hash - 为有限状态自动机接受的语言寻找好的散列函数

Question

我在 Java 项目上工作(但我认为它不依赖于语言)，我在二进制字母表上生成小的(最多 4 个状态)非确定性有限状态自动机，我必须快速检查生成的与前面的等价的自动机。因此，我必须使用一些好的散列函数，以避免与太多的自动机进行比较。

我的第一个想法是对转换进行 DFS 并找到所有接受的单词，直到长度达到最大值。 5 然后我将接受的单词集映射到 64 位长(长度最大为 5 的二进制单词的数量)。但它似乎在具有 4 个状态的 NFA 上产生了太多的冲突。增加长度会导致哈希码的计算速度太慢而无法实际使用。

另一种方法是使用一组单词并测试自动机接受其中的哪些单词，但我认为找到正确的单词并不是那么简单。

您是否知道如何改进散列函数来避免过多的冲突而不显着降低速度？

提前致谢

Answer 1

我在进一步思考(感谢@justhalf 和@templatetypedef)并且我有一个想法 - 任何 NFA(或更准确地说，它接受的语言)对整数的单射函数 - 让我们有一个 NFA A。让我们构造最小的 DFA A_min 接受具有完整 delta 函数的相同语言。作为 Myhill-Nerode 定理的结果，这个自动机除了同构外应该是无歧义的。根据字母表中某些固定的字符顺序(例如第一个 0，第二个 1)，从初始状态开始 BFS，优先考虑边缘(转换)。并根据访问顺序对州重新编号。现在我们有一个规范的最小 DFA，我们可以将状态的关联矩阵映射到一个整数并附加最终状态的枚举(或者更好地制作一个元组，以避免冲突)。这个整数可以用来决定两个 NFA 的等价性。你觉得可以吗，或者有什么其他的想法吗？