java - 从 DFA 中提取语言的算法

Question

我正在尝试寻找一种算法来从 DFA 中提取语言。如果该语言是无限的，那么我只需要报告最多:maxcount <= 1000 个字符串。报告的顺序没有限制。

我试过了:(我不知道怎么写算法所以我只是用文字解释我做了什么)

递归算法 - 对于从一个状态到下一个状态的每次转换，保存转换字符，然后对每个转换进行递归调用，如果该转换是到接受状态，则报告。如果我们达到了“死胡同”然后注意递归。

假设开始状态是state 1，并且有两个转换到:state 2 和state 3，带有转换字符' a','b' 分别。然后有一个从state 3到state 4的转换，转换字符是'c'，只有state 4是一个接受状态。

从 state 1 到 state 2 将保存 'a' as transition character ，但是因为 state 2 是一个死胡同，不会有递归的注意，因为它不是一个接受状态，所以没有报告。

从state 1到state 3会保存'b'然后从state 3到state 4 将保存 'c' 因此我们总共有 "bc" 因为 state 4 确实递归结束时没有任何转换。我们报告 “bc” 因为 state 4 是一个接受状态

---

如果我有带循环的 DFA - 那么为了不“卡在”那个循环中，我确保“如果”有另一个可能的转换，那么我们将始终选择那个转换，而不是我们所做的转换上次/次我们处于那个状态(一种我们在哪个状态下进行的转换的内存)

该算法适用于小型 DFA，但它会在较大的 DFA:s 上产生堆栈溢出(想象从 state 1 到 state 2 的 20 次转换和从 的 30 次转换code>state 2 到 state 3 等等)。

谁能推荐更高效的算法？

Answer 1

1. 运行循环检测算法。
2. 如果没有循环，运行任何路径查找算法(BFS、DFS、Dijkstra、A* 等)以列出从开始到结束的所有路径。
3. 如果有循环运行寻路找到从起始节点到循环的路径。然后输出(循环的起始节点)+(从连接节点开始的循环)* N，其中 N = 1,2,3,...,1000。

或者:

1. 转换为正则表达式。
2. 从正则表达式生成单词。