Good evening, I'm having a serious problem into adapting the following code that is perfectly working to check if a word is accepted or not by a DFA, to make the same check but this time for a NFA. I'm using the accepted function to check whether a string is valid or not for a DFA. Now what I am trying is to make the following check work for a NFA, and I can't figure out what I have to do
Here's what a NFA is : http://ift.tt/1gKVFxs
Here's what a DFA is: http://ift.tt/MkMFAj
For the guys that have asked what a DFA or a NFA is
#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);
}
}
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 << "Finite states: 2, 3" << endl << endl;
cin.get (s,100);
accepted(0, s[0], s, 0);
if (viz[2] == 1) cout << endl << "Accepted";
cout << endl;
return 0;
}
Also here's how my input looks like for the DFA:
4 6
0 0 a
0 1 b
1 2 c
2 2 a
2 3 c
3 3 c
And that's how my input looks like for the NFA:
4 7
0 0 a
0 1 b
1 2 c
2 2 a
2 3 c
3 3 a
3 3 c
Aucun commentaire:
Enregistrer un commentaire