java - 用于从给定 DFA 打印所有接受的字符串(如果数量无限则为上限)的算法

Question

正如标题所述，我正在尝试编写一种算法，根据输入的给定 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 存储库更有用的东西，这些存储库的代码对我来说太复杂了，无法从中学习任何东西。

提前非常感谢!

Answer 1

我将使用表示当前状态和到目前为止生成的字符串的有界对象队列，然后继续执行如下操作，

1. 将 {"", start} 添加到队列中，表示到目前为止创建的字符串(为空)和 DFA 的开始状态。
2. 只要队列中有东西
   1. 从队列前面弹出
   2. 如果当前状态为接受，请将 currentString 添加到结果集中。
   3. 对于从此状态的每次转换，将条目添加到 {currentString+nextCharacter, nextState} 形式的队列中
3. 当您击中足够多的字符串、或者字符串变得太长、或者队列为空时(有限语言)，请停止。