Pergunta sobre nfa, c++, automaton – Projetar um autômato finito não determinístico em c ++ (saída incorreta)

6

Eu estou fazendo uma tarefa para simular um autômato finito não-determinístico, assim como eu explico nestepostar. Eu tenho essa entrada lida do arquivotarea4.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

A primeira linha de entrada é um inteiro T, representado o número de casos para avaliar o programa. Cada caso de teste começa com 4 inteiros, o primeiro é o número de estados do autômato, o próximo é o número de transições do autômato, o terceiro número é o estado inicial e depois o número de estados finais. então vêm os estados finais (no exemplo, os estados finais são 2 e 5). Então vem F linhas, cada uma com um inteiro E, representando E, é um estado final.

Em seguida, vêm N linhas (N é o número de transições), cada um com 2 inteiros e um caractere, I, J e C, representando os estados onde a transição, ou seja, a transição vai do estado i para o estado J com o caractere C. Após esta linha vem com um único inteiro S, que irá conter o número de seqüências para testar, então S linhas com as respectivas seqüências.

a saída esperada é:

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

A saída resultante no meu código:

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

Aqui está meu 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;
}

Minha pergunta é: Por que recebo uma saída incorreta? Eu acho que é para o não-determinismo do autômato definido no caso de teste, mas como eu posso avaliar a string corretamente? Como eu posso mudar minha função chamadaevaluate_string para que de alguma forma verifique os diferentes caminhos que podem levar o autômato a avaliar a cadeia pelo não-determinismo?

Eu tenho sido preso com isso por vários dias e para ser honesto, estou um pouco desesperado.

Por favor, formate seu código corretamente na próxima vez. Seus recortes estavam longe. Além disso, não entendo o resultado esperado. Por exemplo, onde é0 b 3 vindo de? Finalmente, o que você quer? Um NFA ou um DFA? Nada na sua postagem é um autômato determinístico (nem a entrada nem a saída esperada), então removi as menções de “DFA” por enquanto… Konrad Rudolph
@KonradRudolph As transições de estado não importam, estou apenas imprimindo-as para ver o que acontece em cada mudança de estado, o programa simplesmente deve mostrar se a string é aceita ou rejeitada.running the NFA directly is probably easier (not even 10 lines!): a questão é: como eu posso fazer isso ?, estou preso nisso por vários dias. Como devo modificar meu código para fazer isso? novaKid
Não é isso que eu quero dizer. o0 b 3 é da função de transição, não há entrada a considerar. - Quanto à sua pergunta: ah, entendi. A má notícia é: você pode transformar um NFA em um DFA e resolvê-lo, mas não pode obter a saída de transição de estado idêntica porque os nomes dos estadosvai diferem. Além disso, executar o NFA diretamente é provavelmente mais fácil (nem mesmo 10 linhas!) Do que transformá-lo em um DFA primeiro. Konrad Rudolph
where is 0 b 3 coming from?: para a entrada aabbbbcdc as transições do autômato são:(q0, a) = 0, (q0, a) = 0, (q0, b) = 3, (q3, b) = 0, (q0, b) = 3, (q3, b) = 0   'qual você quer?'; Minha função "evaluate_string" implementa um DFA e quero saber como modificá-lo para obter um NFA novaKid

Sua resposta

3   a resposta
1

er qualquer NFA em seu DFA correspondente. Depois de fazer isso, você pode implementar facilmente o autômato, já que os DFAs trabalham de forma determinista.

1

ição assim que você encontrar a transição FIRST válida. O que funcionaria se você estivesse fazendo um DFA, mas um NFA poderia ter vários caminhos válidos.

Duas opções você tem (tenho certeza que existem mais):

1) Implemente um avaliador de NFA: isso envolve acompanhar um conjunto de estados atuais e avaliar cada caractere de entrada em relação a cada estado. Uma vez que a string tenha sido lida, se algum dos estados finais estiver no conjunto, estará completo.

2) Converta o NFA para um DFA, que é, IMHO, a abordagem mais difícil, uma vez que envolve basicamente construir a mesma lógica de conjunto e avaliar as transições para os novos estados.

Ei cara, você deve usar recursão para fazer o NFA ?. Não consigo encontrar o caminho a percorrer, alguma sugestão além do que você indicou para mim? novaKid
Como eu poderia modificar meu código para fazer o que você indica em sua opção 1)Implement an NFA evaluator. Há algum pseudocódigo para fazer ?, tenho muitas dúvidas a lógica do avaliador da NFA. novaKid
@novaKid Leia a postagem de Konrad. Dave S
9

Avaliar um NFA équase tão fácil como avaliar um DFA.

Em um DFA, você tem um estado atual e, em cada etapa, seleciona a próxima transição. No final da entrada, você verifica se o estado atual é um estado de aceitação.

Bem, em um NFA você tem umconjunto dos estados atuais, e em cada passo você passa por todos os estados atuais, e para cada um, você seleciona todas as transições válidas. Esses conjuntos combinados formam seu novo conjunto de estados.

No final, você verifica se a interseção dos estados atuais e dos estados de aceitação não está vazia.

No pseudocódigo, isso é o seguinte:

atual = {inicial }para cada Caracteres em entrada:Próximo = {}para cada Estado em atual:para cada transição em transições[Estado] [Caracteres] ∪transições[Estado] [ϵ]:Próximo.acrescentar(target_of(transição))atual = PróximoE se len(interseção(atual, aceitando))> 0:impressão "String accepted"outro:impressão "String rejected"

Isso pode ser traduzidolinha por linha, em código C ++. Para facilitar, sugiro usarstd::set<int> para ocurrent enext conjuntos e um vetor destd::multimap<char, int> para as transições. Isso pressupõe que cada estado corresponda a um inteiro.

@ajmartin Porra, eu não considerei que ϵ movimentos são transitivos. Obrigado por dedicar seu tempo para rever esta resposta. Infelizmente eu não tenho tempo para corrigi-lo, mas farei isso no futuro próximo. Konrad Rudolph
@ Melkhiah66 O pseudocódigo está correto. Eu peguei 1: 1 de uma implementação em C ++ que funciona como esperado na entrada do OP. A implementação do OP tem um erro nonext.insert(p->second);. Deve ser provavelmentep->first.second. Mas como eu disse, umvector<multimap<char, int>> seria mais fácil (e mais eficiente aqui). Konrad Rudolph
@KonradRudolph Eu não entendo porque você recomenda usar um vetor de vetor multimap <multimap <char, int >>, a estrutura com o código funcionaria perfeitamente. Qual é a diferença ?, Desculpe pela minha insistência franvergara66
@ KonradRudolph Sim, eles fazem. A ramificação virá e haverá máquinas paralelas que operarão na mesma entrada.Verifique isso ajmartin

Perguntas relacionadas