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:

Exemplo de Autômato Finito Não-Determinístico
  • 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).

Exemplo de AFN

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 }

AFN