来自 DFA 的长度为 k 的单词

Question

美好的一天，我在生成一个包含所有长度为 k 的单词的列表时遇到了一个严重的问题（生成函数是用于生成所有长度为 k 的单词的函数，另一个函数用于确定一个单词是否被接受) 仅通过使用 DFS 算法来自 DFA，这是我的尝试：

#include<vector>
#include<iostream>
#include<fstream>
#include<string.h>

using namespace std;

vector < pair <int,char> > a[100];

int viz[100], v[100];
char s1[100];

void accepted (int q, char c, char s[100], int x) {
    c = s[x];
    viz[q] = 1;
    cout << q;
    for (int i = 0; i < a[q].size(); i++)
        if (a[q][i].second == c) {
            x++;
            accepted (a[q][i].first, a[q][i+1].second, s, x);
        }
}

void generate (int q, int k) {
    int x = 0;
    v[q] = 1;
    while (x < k) {
        cout << a[q][0].second;
        for (int i = 0; i < a[q].size(); i++)
            if (v[a[q][i].first] == 0)
            {
                cout << a[q][i].second;
                generate(a[q][i].first, k);
            }
        x++;
    }
}

int main() {
    ifstream f ("input.txt");
    int n, m, x, y, i, j, k;
    char c;
    char s[100];
    f >> n >> m;
    for (i = 0; i < m; i++) {
            f >> x >> y;
            f >> c;
            a[x].push_back (make_pair(y,c));
            }
    for (i = 0; i < n; i++) {
        cout << i << ": ";
        for (j = 0; j < a[i].size(); j++)
            cout << a[i][j].first << a[i][j].second << " ";
        cout << endl;
    }
    cout << endl << "Fiite states: 2, 3" << endl << endl;
    cin.get (s,100);
    accepted(0, s[0], s, 0);
    if (viz[2] == 1) cout << endl << "Accepted";
    cout << endl;
    cin >> k;
    generate (0, k);
    cout << endl;
    return 0;
}

我的输入也是这样的：

DFA 和输出如下所示：

我面临的严重问题是我无法通过调用生成函数将所有获得的单词正确输出到屏幕上。

Answer 1

我更改了您的生成函数，如下所示。接下来是关于我的想法以及我如何改变它的解释。

void generate (int q, int k, string &s) {
    if (k > 0) {
        for (int i = 0; i < a[q].size(); i++)
        {
            s += a[q][i].second;
            generate(a[q][i].first, k-1, s);
            s.pop_back();
        }
    }
    else {
        cout << s << endl;
    }
}

首先，您正在尝试 DFS 的递归和重复版本的混合，但是您没有用于保留堆栈的结构，如果您是，我怀疑，要使用显式堆栈的重复版本。基本上，您的外部 while 循环是错误的，因为 深度应该随着您递归地遍历 图形而增加，而不是像您那样使用 while 循环在单个递归级别重复。正如我提到的，您还可以采用重复方法并使用显式定义的堆栈，而不是递归实现 DFS 时内存隐式使用的堆栈。但是通过递归实现更容易、更直观地掌握 DFS，所以我省略了外循环。

其次，保留访问节点列表不是一个好主意，因为您想列出所有 k 长度字符串并且 您的 DFA 不是一个简单的图。（即可能存在从节点 u 到节点 u 的边）所以我删除了 for 循环内的 if 语句，因为您可以多次访问正常节点。您的方法是基于 DFA 的分支因子的指数，但是如果您的 k 足够小，那么无论如何它都应该起作用。并且指数方法不是您正在寻找这个问题的解决方案的问题。

第三，可能是由于您使用了 while 循环，在每个级别打印单个字符时出现了混淆，这是不正确的。请记住，在每个深度为 k 的节点，您必须打印所有您遇到的字符，从树的根部开始。这就是为什么我将一个字符串作为第三个参数添加到您的函数中。不过别担心，它是通过引用传递的，它只会给你的算法增加 O(k) space 复杂度，这应该可以忽略不计。

如果在您的主函数中使用下面的调用开始遍历，您会发现它可以正常工作。

string S;
generate(0, k, S);

来自 DFA 的长度为 k 的单词

Words of length k generation from a DFA

c++

algorithm

dfa

c++11

c++14