用于从给定DFA打印所有接受字符串（如果数量无限，则打印到上限）的java算法
正如标题所述，我正在尝试编写一个算法，该算法根据输入上给定的DFA（确定性有限自动机）生成一个上界的可接受字符串
如果它包含循环模式，那么它不应该生成比上限n更多的字符串，因为显然我不能打印无限多的字符串，这导致了我的问题
使用有限语言的机器非常直截了当，因为我可以进行DFS搜索，遍历图形，并将所有递归连接状态的字母连接起来，但是我不知道应该如何处理无限语言dfa，除非我硬编码了DFS应该遍历可能导致循环的状态的次数限制
所以我的问题是,；我们应该如何着手解决这个问题。有什么已知的算法可以用来解决这个问题吗？ 绑定指定字符串的数量，而不是长度。字符串长度不允许超过5000个字符，但最好不要接近该长度，因为在测试中，n的最大界限最多为1000个字符
我目前非常天真的解决方案如下：
public void generateStrings(int currentStateNum, Set<String> output, String prefix, Set<Integer> traversedStates){
State currentState, tempState;
String nextString;
currentState = dfa.get(currentStateNum);
//keeps track of recursion track, i.e the states we've already been to.
//not in use because once there are cyclic patterns the search terminates too quickly
//traversedStates.add(currentStateNum);
//My current, bad solution to avoid endless loops is by checking how many times we've already visited a state
currentState.incrementVisited();
//if we're currently looking at an accepted state we add the current string to our list of accepted strings
if(currentState.acceptedState){
output.add(prefix);
}
//Check all transitions from the current state by iterating through them.
HashMap<Character, State> transitions = currentState.getTransitions();
for (Map.Entry<Character, State> table : transitions.entrySet()) {
//if we've reached the max count of strings, return, we're done.
if (output.size() == maxCount) {
return;
}
tempState = table.getValue();
//new appended string. I realize stringbuilder is more efficient and I will switch to that
//once core algorithm works
nextString = prefix + table.getKey().toString();
//my hardcoded limit, will now traverse through the same states as many times as there are states
if (tempState.acceptedState || tempState.getVisitedCount() <= stateCount) {
generateStrings(tempState.getStateNum(), output, nextString, traversedStates);
}
}
}
它不是一个真正的dfs，因为我不检查我已经访问过的状态，因为如果我这样做，将打印的所有内容都是最简单的到最近接受状态的路径，这不是我想要的。我希望根据需要生成尽可能多的字符串（如果DFA的语言不是有限的，也就是说）
这个解决方案一直有效，直到我任意选择的“访问限制”不再减少为止，所以我的解决方案在某种程度上或完全不正确
正如您所看到的，表示自动机的数据结构是一个带有状态的ArrayList，其中State是一个单独的类，它包含一个带有转换的HashMap，其中键是edge char，值是转换导致的状态
有人知道我应该如何处理这个问题吗？我试图找到类似的问题，但我找不到比一些github repos更有用的东西，这些代码太复杂了，我无法从中学习
提前多谢
# 1 楼答案
我将使用一个有界的对象队列来表示当前状态和到目前为止生成的字符串，然后进行如下操作：