Слова длины k поколения из DFA
Добрый день,
У меня возникла серьезная проблема при создании списка со всеми словами длины k (функция генерирования — это функция, предназначенная для генерации всех слов длины k, другая функция используется, чтобы узнать, принято слово или нет ) из DFA, просто используя алгоритм DFS, вот моя попытка:
#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;
}
Также вот как выглядит мой вклад:
4 6
0 0 a
0 1 b
1 2 c
2 2 a
2 3 c
3 3 c
Вот как будут выглядеть DFA и выходные данные:
Серьезная проблема, с которой я сталкиваюсь, заключается в том, что я не могу найти способ правильно выводить все полученные слова на экран, вызывая функцию generate.
Решение
Я изменил вашу функцию генерации, как показано ниже. Ниже приводится объяснение того, что я думал и как я это изменил.
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) Поэтому я удалил оператор if внутри цикла for, чтобы вы могли посещать вменяемый узел несколько раз. Ваш подход экспоненциальный, основанный на коэффициенте ветвления DFA, но если ваш k достаточно мал, он должен работать независимо от этого. И экспоненциальный подход не является проблемой, решение которой вы ищете в этом вопросе.
В-третьих, возможно, из-за того, что вы использовали цикл while, произошла путаница с печатью одного символа на каждом уровне, что неверно. Помните, на каждом узле глубины k, ты должен распечатать все символы, с которыми вы столкнулись, начиная с корня дерева. Вот почему я добавил строку в качестве третьего параметра для вашей функции. Не волнуйтесь, хотя, это передается по ссылке, и это только приведет к добавлению Хорошо) Пространственная сложность вашего алгоритма, которая должна быть незначительной.
Если в вашей основной функции вы начнете обход с помощью вызова ниже, вы обнаружите, что он работает правильно.
string S;
generate(0, k, S);
Другие решения
Других решений пока нет …