正如标题所述,我正在尝试编写一种算法,根据输入的给定 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,其中键是边缘字符,值是转换导致的状态。有谁知道我应该如何处理这个问题?我努力寻找类似的问题,但我找不到比一些 github 存储库更有用的东西,这些存储库的代码对我来说太复杂了,无法从中学习任何东西。
提前非常感谢!
最佳答案
我将使用表示当前状态和到目前为止生成的字符串的有界对象队列,然后继续执行如下操作,
- 将 {"", start} 添加到队列中,表示到目前为止创建的字符串(为空)和 DFA 的开始状态。
- 只要队列中有东西
- 从队列前面弹出
- 如果当前状态为接受,请将 currentString 添加到结果集中。
- 对于从此状态的每次转换,将条目添加到 {currentString+nextCharacter, nextState} 形式的队列中
- 当您击中足够多的字符串、或者字符串变得太长、或者队列为空时(有限语言),请停止。
关于java - 用于从给定 DFA 打印所有接受的字符串(如果数量无限则为上限)的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51986329/