查找 DFA 的所有匹配项

Question

给定一个 DFA（确定性有限自动机），我可以使用什么算法来生成自动机接受的所有输入序列的流，并按长度升序排序？

Answer 1

如果您有权访问 DFA 的属性（即状态、转换、开始状态、接受状态），则让算法将该信息转换为图形，其中状态是顶点，转换被标记为边（标记为输入符号）。

从起始节点开始进行广度优先遍历，允许重新访问节点。每当访问表示接受状态的节点时，输出与路径对应的字符串。在扩展搜索时跟踪形成的字符串，或者保留对路径中前面节点的反向引用，以便可以从该链表重建字符串。

如果必须为大小相同的字符串对输出进行排序，则确保节点的传出边按标签（符号）排序。

这不是一种节省内存的方法。

如果 DFA 接受无限数量的输入，则此算法将 运行 无限，但实际上它将 运行 直到 运行 内存不足。