Diseñe un autómata finito no determinista en C++ (salida incorrecta)

Question

Estoy haciendo una tarea para simular un autómata finito no determinista, tal como explico en este post. Tengo esta entrada de leer el archivo tarea4.in:

1 
6 8 0 2 
2 
5 
0 0 a 
0 1 a 
1 1 b 
1 2 c 
1 3 c 
3 4 d 
4 4 d 
4 5 d 
5 
aaabcccc 
aabbbbcdc 
abbcdddcc 
acdddddd 
abc 

La primera línea de entrada es un entero T, representa el número de casos para evaluar el programa. Cada caso de prueba comienza con 4 enteros, el primero es el número de estado del autómata, el siguiente es el número de transiciones del autómata, el tercer número es el estado inicial y luego el número de estados finales. luego vienen los estados finales (en el ejemplo, los estados finales son 2 y 5). Luego vienen las líneas F, cada una con un número entero E, que representa E es un estado final.

Luego vienen N líneas (N es el número de transiciones), cada una con 2 enteros y un carácter, I, J y C, representando los estados donde la transición, es decir, la transición va del estado i al estado J con el carácter C. Siguiendo esta línea, viene con un entero único S, que contendrá el número de cadenas para probar, luego S líneas con las cadenas respectivas.

la salida esperada es:

Test Case #2: 
aaabcccc Rejected 
aabbbbcdc Rejected 
abbcdddcc Rejected 
acdddddd Accepted 
abc Accepted 

La salida resultante en mi código:

Test Case #1: 
aaabcccc Rejected 
aabbbbcdc Rejected 
abbcdddcc Rejected 
acdddddd Rejected 
abc Rejected 

Aquí está mi código:

#include <iostream> 
#include <vector> 
#include <map> 
#include <set> 
#include <utility> 
#include <vector>  
using namespace std; 

typedef map<pair<int, int>, char> transitions; 
    transitions trans; 

    int numberFinals; 
    vector<int> currentStates;  

int main(){ 

    freopen ("tarea4.in", "r", stdin); 
    //freopen ("tarea4.out", "w", stdout);   
    int testCases, i, j,k, cont=1,finalStates,numberInputs,stateOrigin, stateDestination; 
    int numberStates, numberTransitions, initialState; 
    char transitionCharacter ; 

    set<int> current; 
    set<int> next; 
    set<int>::iterator it; 
    set <int> final; 
    std::set<int> the_intersection; // Destination of intersect 
    map<pair<int, int>, char>::iterator p; 
    string inputString; 

    cin>> testCases; 
    for (i=0;i< testCases;i++){ 
     cin>>numberStates>>numberTransitions>>initialState>>numberFinals; 
     current.insert (initialState); 

     for (j=0;j<numberFinals;j++){ 
      cin>>finalStates; 
      final.insert(finalStates); 
     } 

     for (j=0; j<numberTransitions;j++){ 
      cin>> stateOrigin>>stateDestination>>transitionCharacter; 
      trans.insert(transitions::value_type(std::make_pair(stateOrigin, stateDestination), transitionCharacter)); 
     } 

     cin>>numberInputs; 

     cout<<"Test Case #"<<cont++<<":"<<endl;  

     for (j=0; j<numberInputs;j++){ 
      //////////////////the code of the answer ///////////////// 
      current.insert (initialState); 
      cin>> inputString; 
      cout<<inputString<<" "; 


    for (k=0; k<str.size();k++){ 
     next.clear(); 
     for (it=current.begin() ; it != current.end(); it++){ 
       for (q= trans.begin(); q!= trans.end();q++){ 
        if((*it == q->first.first)&&(str[k]==q->second)){ 
        next.insert(q->first.second); 
        } 
       current=next; 
       } 
     } 
    } 

      std::set_intersection(current.begin(), current.end(), final.begin(), final.end(), std::inserter(the_intersection, the_intersection.end())); 

      if (the_intersection.size()>0){ 
       cout<< "Accepted"<<endl; 
      } 
      else{ 
       cout<< "Rejected"<<endl; 
      } 

     } 

     printf ("\n"); 
    } 

return 0; 
} 

Mi pregunta es: ¿Por qué aparece incorrecta ¿salida? Creo que es por el no determinismo del autómata definido en el caso de prueba, pero ¿cómo puedo evaluar la cadena correctamente? ¿Cómo puedo cambiar mi función llamada evaluate_string para que de alguna manera compruebe las diferentes rutas que puede tomar el autómata para evaluar la cadena por el no determinismo?

He estado atascado con esto durante varios días y para ser sincero, estoy algo desesperado.

Answer 1

Evaluar un NFA es casi tan fácil como la evaluación de un DFA.

En un DFA, tiene un estado actual y en cada paso selecciona la siguiente transición. Al final de la entrada, verifica si el estado actual es un estado de aceptación.

Bueno, en un NFA tiene un conjunto de estados actuales, y en cada paso pasa por todos los estados actuales, y para cada uno, selecciona todas las transiciones válidas. Esos conjuntos combinados forman su nuevo conjunto de estados.

Al final, verifica si la intersección de los estados actuales y los estados de aceptación no está vacía.

En Pseudo-código este es el siguiente:

• actual = { inicial}
• para cada Charen entrada:
  • siguiente = {}
  • para cada estadoen actual:
    • para cada transiciónen transiciones [ estatales] [ carbonilla] ∪ transiciones [ estado] [ ε]:
      • siguiente. anexar ( target_of ( transición))
  • actual = siguiente
• si len ( intersección ( actual, aceptar))> 0:
  • de impresión"String accepted"
• demás:
  • de impresión"String rejected"

Este puede traducirse, línea por línea, en código C++.Para hacerlo más fácil, sugiero usar std::set<int> para los conjuntos current y next, y un vector de std::multimap<char, int> para las transiciones. Esto supone que cada estado corresponde a un número entero.

Answer 2

Creo que primero debe implementar el mecanismo general para convertir cualquier NFA a su DFA correspondiente. Después de hacer eso, puede implementar fácilmente el corredor automático ya que los DFA funcionan de manera determinista.

Answer 3

El problema fundamental es que su código está saliendo del ciclo de transición tan pronto como encuentre la PRIMERA transición válida. Lo cual funcionaría si estuvieras haciendo un DFA, pero un NFA podría tener múltiples rutas válidas.

dos opciones que tiene (estoy seguro de que hay más):

1) Implementar un evaluador NFA: Se trata de hacer el seguimiento de un conjunto de estados actuales, y la evaluación de cada carácter de entrada frente a cada estado. Una vez que se ha leído la cadena, si alguno de los estados finales está en el conjunto, está completa.

2) Convierta el NFA en un DFA, que es, en mi humilde opinión, el enfoque más difícil, ya que básicamente implica construir la misma lógica de conjunto y evaluar las transiciones para los nuevos estados.