Проверьте, принята ли строка NFA

Question

Проверьте, принята ли строка NFA

Я пытаюсь создать функцию, чтобы узнать, принята ли строка NFA или нет, и я не могу найти правильный способ сделать это.

Вот как выглядит мой вклад:

Вот как выглядит моя программа в данный момент:

#include<vector>
#include<iostream>
#include<fstream>
#include<cstring>

using namespace std;

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

ifstream g ("input.txt");

int n, m, x, y, ok = 0;
char c;

void reading () {
g >> n >> m;
for (int i = 0; i < m; i++) {
g >> x >> y;
g >> c;
w[x].push_back (make_pair(y,c));
}
}

void show () {
for (int i = 0; i < n; i++) {
cout << i << ": ";
for (int j = 0; j < w[i].size(); j++)
cout << w[i][j].first << w[i][j].second << " ";
cout << endl;
}
}

int main () {
char s[100];
reading ();
show ();
cin.get (s2, 100);
int wl = strlen(s2);
if (nfa (0, s2[0], s2, 0, wl) == true) cout << "Accepted";
else cout << "Not accepted";
return 0;
}

Вот форма NFA:

Вот функция, которую я пытался создать:

bool nfa (int q, char c, char s[100], int x, int wl) {
if(x == wl){
return (q == 0 || q == 2); //current state is accepting state and we're at the end of the word
}

c = s[x];
//viz[q] = 1; this line becomes useless
//cout << q;
for (int i = 0; i < a[q].size(); i++)
if (a[q][i].second == c) {
//x++;
if(nfa (a[q][i].first, a[q][i+1].second, s, x + 1, wl))
return true;
}

return false;
}

Я был бы более чем благодарен, если бы кто-то мог предоставить решение для этой программы

Спасибо!

-4

algorithm c++c++11 c++14 nfa

Решение

Другие решения

Зачем вообще напрягаться? Каждый NFA соответствует регулярному выражению. Просто проверьте, соответствует ли регулярное выражение входной строке, и все готово.

Если вы настаиваете на дополнительных затратах на создание NFA, для этой проблемы есть довольно простые шаблоны проектирования.

Что касается вашего алгоритма, здесь есть несколько проблем:

Функция nfa будет применимо для DFA, но пример машины — NFA. Проблема, скорее всего, вызвана этой строкой:

if (a[q][i].second == c) {
x++; //<-- this line causes incorrect behavior

Поскольку ваша машина является NFA, может быть несколько совпадений для if-clause. Или другими словами: в NFA может существовать более одного перехода состояния для определенного узла и входного значения. Например. в вашем примере-машина:

0 -->b {0 , 3}

Но ваш алгоритм будет увеличиваться x каждый раз, когда встречается узел. Поэтому для первого узла мы продолжим поиск правильного следующего входного символа (index = x + 1). Следующий узел, который найден и для которого существует соответствующий переход состояния, будет продолжен со следующим (неправильным) входным символом (index = x + 2). Простое решение этого было бы следующим:

if (a[q][i].second == c) {
//x++; remove this line
nfa (a[q][i].first, a[q][i+1].second, s, x + 1);//note the x + 1
}

Следующая проблема:
Вы создали рекурсивный метод без условия завершения, который пересекает массив, чтобы сделать вещи хуже. Алгоритм просто выйдет за пределы массива и вызовет ошибку сегментации.

Добавьте такое условие в начале nfa:

if(x == 100){ //alternatively use a more variant bound
//end of the string
return;
}

Чтобы предотвратить запуск машины через границы массива.

РЕДАКТИРОВАТЬ:
Есть еще одно неправильное представление об использовании viz[q], Это только держит посещенный флаг для каждого государства. Но НФА принимает только слово, если оно привалы в принимающем состоянии, которое не может быть определено viz[q], поскольку установлен флаг посещения, если машина когда-либо находится в состоянии q, Вместо этого вы должны использовать bool возвращаемое значение, чтобы определить, остановился ли компьютер в состоянии принятия:

bool nfa (int q, char c, char s[100], int x) {
if(x == 100){
return (q == 0 || q == 2); //current state is accepting state and we're at the end of the word
}

c = s[x];
//viz[q] = 1; this line becomes useless
cout << q;
for (int i = 0; i < a[q].size(); i++)
if (a[q][i].second == c) {
//x++;
if(nfa (a[q][i].first, a[q][i+1].second, s, x + 1))
return true;
}

return false;
}

Обратите внимание, что эта машина будет принимать только слова длиной 100. Если вы хотите, чтобы машина принимала слова произвольной длины, вам придется реорганизовать условие завершения, чтобы остановить, если достигнут конец слова, так:

if(x == word_length){
return ...
}

wordLength может быть дополнительным параметром nfa,

1

Источник

Accepted Answer

Я настоятельно рекомендую использовать Государственный аппарат для вашей реализации.

Стол может очень помочь с реализацией.

Я обычно использую таблицу (массив):

struct State_Record
{
State_Type    present_state;
Input_Type    input;
State_Type    destination_state; // A.k.a. transition
};

Если для текущего состояния найдены входные данные, присвойте текущее состояние состоянию назначения.

Вы могли бы далее разделить это. Например, используя std::map<Input_Type, State_Type> который будет сопоставлять входные значения с состояниями назначения.

Кроме того, поищите в интернете «Пример шаблона State Machine C ++».

Примечание: я использую таблицу, потому что я могу определить данные как постоянные, чтобы не тратить время на инициализацию структур при инициализации, таких как использование std::map, Кроме того, компилятор может поместить данные в область памяти, доступную только для чтения, и получить доступ к данным напрямую.

1