Implementare AFN

[•mitzu2250]

Salut, intampin unele dificultati la implementarea unui algoritm pentru un Automat Finit Nedeterminist. Vreau sa il reprezint printr-o matrice tridimensionala unde: liniile (i) sunt starile, coloanele (j) sunt literele alfabelului si in adancime (k) sunt posibilitatile.

Matricea este construita astfel: daca pentru un element sunt mai multe posibilitati in matrice pe pozitia a[ i ][0][j] sunt numarul posibilitatilor apoi pe a[ i ][k>1][j] sunt posibilitatile in care se poate ajunge din starea i aplicand actiunea j.

De la tastatura se citeste un sir de caractere de exemplu "01" (valid) "000111" (valid) "02" (valid) "012" (invalid) si trebuie sa determin daca se ajunge sau nu intr-o stare finala.

Codul pana acum este:

Cod:

// AFN
#include <fstream>
#include <stdlib.h> 
#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int n,m,i,j,k,q,x,f[100],a[10][10][10],curent,merge,y,cuv,alfa=0,pos,anterior,save;
    char c[100],stari[10]={'a','b','c'};
    
    fstream fi("AFN.in", ios::in);
    
    cout<<"Numar Stari: "; fi>>n; cout<<n<<endl;
    cout<<"Numar Simboluri: "; fi>>m; cout<<m<<endl;
    cout<<endl;
    cout<<"Starea initiala: "; fi>>q; cout<<q<<endl;
    cout<<endl;
    cout<<"Numar Stari finale: "; fi>>x; cout<<x<<endl;
    
    for(i=0;i<x;i++)
     {cout<<"Starea finala "<<i+1<<": "; fi>>f[i]; cout<<f[i]<<endl;}
    
    cout<<endl;
    
    for(i=0;i<n;i++)
     for(j=0;j<m;j++)
     {fi>>pos; a[i][0][j]=pos;
      for(k=1;k<=a[i][0][j];k++)
       {cout<<stari[j]<<" aplicat starii "<<i<<" merge in: "; fi>>a[i][k][j]; if(a[i][k][j]!=-1) cout<<a[i][k][j]<<endl; else cout<<"-"<<endl;}}
     
    cout<<endl;
      
    for(i=0;i<n;i++)
    {for(j=0;j<m;j++)
      {for(k=1;k<=a[i][0][j];k++)
        cout<<a[i][k][j]<<" ";
	   if(a[i][0][j]==-1) cout<<" - ";
       cout<<" | ";}
      cout<<endl;}
     
    cout<<endl;
    
    for(i=0;i<m;i++)
    cout<<i<<"-"<<stari[i]<<"  ";
    
    cout<<endl<<endl;
//pana aici merge bine, de aici este gresit!
    cout<<"Numar cuvinte: "; cin>>cuv;
    for(j=0;j<cuv;j++)
    {cin>>c; 
     curent=q;
	
	 for(i=0;i<strlen(c);i++)
	  {y=c[i]-48; //ca sa transforme din cifre in litere, ma rog, merge chestie
	 curent=a[curent][k?][y];
	   
	  }

	  
	  cout<<curent<<"      ";
	 
	 merge=0;     
     for(i=0;i<x;i++)
      if(curent==f[i]) merge=1;
	
    
    
    
    if(merge==1) cout<<"ACCEPTAT!"<<endl<<endl;
        else cout<<"NEACCEPTAT!"<<endl<<endl;
        
     alfa=0;
        
    for(i=0;i<strlen(c);i++)
     {y=c[i]-48; if(y>=m) alfa=1;}
     
    if(alfa==1) cout<<"    CARACTER GRESIT!"<<endl;
    }
    
    system("pause");
    
 return 0;         
}

Un fisier de intrare ar arata astel:

Cod:

5 3
0

2 2 4

2 1 3 -1 -1
1 1 1 2  -1
-1 1 2  -1
1 3 -1 1 4
 -1  -1 1 4

Acest fisier este pentru AFN-ul urmator:


In principiu, nu reusesc sa fac parcurgerea si in final verificarea daca dupa ce s-a citit sirul respectiv. Nu stiu cum sa fac ca atunci cand nu mai are alte variante de parcurgere sa se intoarca sa o ia pe alta ramura [varianta cu "01" imi merge dar pentru "02" se blocheaza deoarece nu o ia pe ramura de jos]

[•PlayLikeNeverB4]

E destul de usor cu o functie recursiva, gen http://www.infoarena.ro/problema/dfs.