lundi 28 mars 2016

Check if a string is accepted or not by an NFA [on hold]

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