2.2 Autômatos Não-determinísticos (AFNs)
Em outros livros, este tipo de autômato pode ser chamado de autômato finito não-determinístico
com transições vazias (AF, AFND- ou NFA).
Este modelo de computação é uma extensão dos AFDs (ou seja, ele permite tudo o que os AFDs
permitem e algo mais). Em relação aos AFDs, os AFNs permitem duas novas características:
- Transições múltiplas para um mesmo símbolo
Exemplo: No autômato abaixo, partindo de q0 e lendo ‘a’ o autômato pode mudar para:
q0, q1 ou q3.
- Transições sem ler símbolo (transição vazia ou transição )
Exemplo: no autômato abaixo, partindo do estado q0, é possível ir sem ler símbolo para:
q1 ou q2 (ou pode ficar parado em q0).
Determinismo x Não-determinismo:
- Um AFD efetua exatamente uma transição para cada par (estado, símbolo). Logo, um
AFD permite apenas uma computação (um caminho no autômato) para uma dada cadeia
de entrada.
o A computação é “bem determinada”.
- Um AFN pode ter mais de uma opção de transição por para (estado,símbolo). Logo po-
de seguir também mais de uma computação para uma cadeia de entrada.
o A computação a ser seguida não é “bem determinada”.
Diremos que um AFN X aceita uma cadeia w se existir pelo menos uma computação em que:
- X lê toda a cadeia w, e
- Ao final da leitura, termina em um estado de aceitação de X.
Diremos que um AFN X rejeita uma cadeia w se não existir nenhuma computação que satisfaça
as condições acima.
Conceitualmente, um AFN representa/decide linguagens ou resolve/decide problemas da mesma
forma que um AFD.
Exemplo: considerando o alfabeto {a,b}, segue o AFN chamado N1, tal que:
L(N1) = { w | w tem a subcadeia aa }
