Pregunta sobre c++, nfa, automaton – Diseñar un autómata finito no determinístico en c ++ (salida incorrecta)

6

Estoy haciendo una tarea para simular un autómata finito no determinista, tal como explico en esteenviar. Tengo esta entrada leída del archivotarea4.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, representado el número de casos para evaluar el programa. Cada caso de prueba comienza con 4 enteros, el primero es el número de estados para el 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 entero E, que representa E es un estado final.

Luego vienen las líneas N (N es el número de transiciones), cada una con 2 enteros y un carácter, I, J y C, que representan los estados donde se encuentra la transición, es decir, la transición va del estado i al estado J con el carácter C. Siguiendo esta línea, venga con un solo número entero S, que contendrá el número de cadenas a probar, luego las líneas S 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é obtengo una salida incorrecta? 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 llamadaevaluate_string ¿De que de alguna manera verifique los diferentes caminos que puede tomar el autómata para evaluar la cadena por el no determinismo?

Me he quedado estancado con esto durante varios días y, para ser honesto, estoy algo desesperado.

where is 0 b 3 coming from?: para la entrada aabbbbcdc las transiciones del autómata son:(q0, a) = 0, (q0, a) = 0, (q0, b) = 3, (q3, b) = 0, (q0, b) = 3, (q3, b) = 0   '¿Cuál quieres?'; Mi función "evaluar_string" implementa un DFA y quiero saber cómo modificarlo para obtener un NFA novaKid
@KonradRudolph Las transiciones de estado no importan, solo las estoy imprimiendo para ver qué sucede en cada cambio de estado, el programa simplemente debe mostrar si la cadena es aceptada o rechazada.running the NFA directly is probably easier (not even 10 lines!): la pregunta es: ¿cómo puedo hacer esto? Estoy atascado en esto durante varios días. ¿Cómo debo modificar mi código para hacer esto? novaKid
Por favor, formatee su código correctamente la próxima vez. Tus hendiduras estaban muy lejos. Además, no entiendo el resultado esperado. Por ejemplo, donde está0 b 3 ¿procedente de? Finalmente, ¿qué quieres? ¿Un NFA o un DFA? Nada en tu publicación es un autómata determinista (ni la entrada ni la salida esperada), por lo que he eliminado las menciones de "DFA" por ahora ... Konrad Rudolph
Eso no es lo que quiero decir. los0 b 3 es de la función de transición, no hay entrada a considerar. - Con respecto a tu pregunta: ah, lo tengo. La mala noticia es que puede transformar un NFA en un DFA y resolverlo, pero no puede obtener la salida de transición de estado idéntica de eso porque sus nombres de estadoserá diferir de. Además, ejecutar la NFA directamente es probablemente más fácil (¡ni siquiera 10 líneas!) Que transformarlo primero en una DFA. Konrad Rudolph

Tu respuesta

3   la respuesta
9

La evaluación de un NFA escasi tan fácil como evaluando 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 una NFA tienes unaconjunto de los estados actuales, y en cada paso recorre 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 esto se ve como sigue:

corriente = {inicial }para cada carbonizarse en entrada:siguiente = {}para cada estado en corriente:para cada transición en transiciones[estado] [carbonizarse] ∪transiciones[estado] [ϵ]:siguiente.adjuntar(target_of(transición))corriente = siguienteSi len(intersección(corriente, aceptando))> 0:impresión "String accepted"más:impresión "String rejected"

Esto se puede traducir,linea por linea, en código C ++. Para hacer esto fácil, sugiero usarstd::set<int> Para elcurrent ynext conjuntos, y un vector destd::multimap<char, int> para las transiciones. Esto supone que cada estado corresponde a un entero.

@KonradRudolph Sí, lo hacen. La ramificación vendrá y habrá máquinas paralelas que operarán en la misma entrada.Mira esto ajmartin
@novaKid Uuuh, tienes razón. Debería ser. Lo he arreglado. Konrad Rudolph
@KonradRudolph Su algoritmo no cubreMoves-se mueve ajmartin
Edité el código de la pregunta, realicé los cambios que indicó en su respuesta, pero todavía obtengo un resultado correcto. ¿Qué estoy haciendo mal al implementar tu soluicón? Traduje el pseudocódigo al lenguaje c + + usando set como usted indicó, pero todavía veo qué diablos estoy haciendo mal. ¿Alguna ayuda en esto? novaKid
1

cualquier NFA a su DFA correspondiente. Después de hacer eso, puede implementar fácilmente un autómata ya que los DFA funcionan de manera determinista.

1

ansición tan pronto como encuentre la PRIMERA transición válida. Lo que funcionaría si estuviera haciendo un DFA, pero un NFA podría tener múltiples rutas válidas.

Dos opciones que tienes (estoy seguro que hay más):

1) Implementar un evaluador de la NFA: esto implica realizar un seguimiento de un conjunto de estados actuales y evaluar cada carácter de entrada contra cada estado. Una vez que se ha leído la cadena, si alguno de los estados finales está en el conjunto, está completo.

2) Convierta la NFA a una DFA, que es, en mi 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.

@novaKid Lee la publicación de Konrad. Dave S
Hola hombre, ¿debes usar la recursión para hacer la NFA? No puedo encontrar el camino a seguir, ¿alguna sugerencia aparte de lo que me indicó? novaKid
¿Cómo podría modificar mi código para hacer lo que usted indica en su opción 1)Implement an NFA evaluator. ¿Hay algún pseudocódigo que hacer ?, tengo muchas dudas sobre la lógica del evaluador de la NFA. novaKid

Preguntas relacionadas