Simulação de um autômato não determinístico
Se temos um autômato não determinístico e queremos descobrir se ele aceita uma palavra dada, podemos converter o autômato em determinístico, podemos tentar de algum jeito ou podemos usar um algoritmo que simula o funcionamento do AFN.
Princípio do algoritmo
Vamos mostrar o princípio com um exemplo adequado. Considere este autômato:
Trata-se de um autômato finito não determinístico que aceita alguma linguagem. Não precisamos nos preocupar agora com qual. Vamos mostrar como pode ser a computação desse autômato para a palavra de entrada 11001. O raciocínio será este: processamos um símbolo da palavra e vemos para onde podemos ir, graças às várias transições para o mesmo símbolo. Memorizamos todos esses estados e, no passo seguinte, já vamos supor que estamos “em todos esses estados ao mesmo tempo”, e vai nos interessar para onde podemos ir a partir desses estados.
Vamos, então, memorizar o conjunto de estados em que podemos estar e a parte não lida da palavra. No começo temos, assim, o par ⟨{q0}, 11001⟩. Começamos no estado q0 (estado inicial) e na entrada está a palavra 11001. O autômato fica assim, com o estado em que estamos destacado em vermelho e em negrito:
O primeiro símbolo é 1; do estado q0 há apenas uma transição para o símbolo 1, então chegamos ao estado q1. Memorizamos o par ⟨{q1}, 1001⟩. O autômato fica assim:
Continuamos. A parte não lida da palavra tem a forma 1001, então de novo procuramos transições para 1. Agora são duas — uma de volta ao estado q0 e outra para o estado q3. Nós agora seguimos para os dois estados ao mesmo tempo. Memorizamos, assim, o par ⟨{q0, q3}, 001⟩.
Qual é a lógica disso? Sabemos que existe um caminho para, a partir do estado inicial, chegar com a palavra 11 tanto ao estado q3 quanto ao estado q0. Ainda não sabemos qual ramo vai nos servir, então simplesmente memorizamos os dois. Continuamos. Na entrada temos o símbolo 0. Agora precisamos olhar tanto para as transições de q0 quanto para as de q3. Do estado q0 saem transições para os estados q1 e q2, e do estado q3 sai uma transição de volta para q1. Contabilizamos todos esses estados e obtemos o par ⟨{q1, q2}, 01⟩:
Mas ainda não terminamos esse passo. Vemos que do estado q2 sai uma transição ε para o estado q4. Sabemos que, depois de uma transição ε, podemos “ir a qualquer momento”, sem ler outro caractere. Em outras palavras — sem ler outro símbolo da palavra de entrada, ainda podemos passar para o estado q4. Acrescentamos, então, o estado q4 entre os estados em que podemos estar: ⟨{q1, q2, q4}, 01⟩. Pintaríamos o autômato assim:
Em seguida, na entrada está 0. Vemos para onde podemos ir a partir dos três estados em que estamos. De q1 não podemos ir a lugar nenhum, porque falta a transição para 0. A computação nesse ramo termina. Do estado q4 também não vamos a lugar nenhum. Do estado q2 voltamos para o estado q2. Mas, como de novo do estado q2 sai uma transição ε para o estado q4, podemos chegar também ao estado q4. Do conjunto de estados {q1, q2, q4}, com o símbolo 0, podemos então chegar ao conjunto de estados {q2, q4}, e obtemos o par ⟨{q2, q4}, 1⟩:
Por fim, na entrada temos o símbolo 1. Do estado q2 não vamos a lugar nenhum, e a computação nesse ramo termina. Mas do estado q4 chegamos aos estados q3 e q5. Obtemos o par ⟨{q3, q5}, ε⟩:
Agora o autômato leu a palavra inteira e “se encontra” em dois estados: q3, q5. Como pelo menos um deles é um estado final, o autômato aceita a palavra 11001.
Algoritmo
Primeiro precisamos de uma função que receba como parâmetro um conjunto de estados e calcule para quais estados ainda podemos ir por meio de transições ε. A entrada é, assim, o autômato ⟨Q, Σ, δ, q0, F⟩ e um conjunto de estados States, e a saída é um superconjunto desses estados, formado pelos estados a que se pode chegar por transições ε. Vamos chamar essa operação de fecho ε do conjunto States.
Vamos usar essa função na função que simulará o funcionamento do autômato não determinístico. A entrada é o autômato, a palavra de entrada w = w1w2… wn e o conjunto de estados em que o autômato se encontra no momento. A saída é a resposta Sim ou Não, conforme o autômato aceite ou não a palavra dada.
Se quisermos verificar se o autômato aceita a palavra w, chamamos a função assim: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0})).
Fontes
Capítulos: Autômato finito, Autômato completo, Autômato finito não determinístico, Simulação de um autômato não determinístico, Conversão de AFN em AFD
