• NFA significa autômatos finitos não determinísticos. É mais fácil construir um AFN do que um AFD para uma determinada linguagem regular.
• Os autômatos finitos são chamados de NFA quando existem muitos caminhos para entradas específicas do estado atual para o próximo estado.
• Todo AFN não é AFD, mas cada AFN pode ser traduzido em AFD.
• O NFA é definido da mesma forma que o DFA, mas com as duas exceções a seguir, ele contém vários próximos estados e contém transição ε.

Na imagem a seguir, podemos ver que do estado q0 para a entrada a, existem dois próximos estados q1 e q2, da mesma forma, de q0 para a entrada b, os próximos estados são q0 e q1. Portanto, não é fixo ou determinado qual será o próximo passo com uma determinada entrada. Portanto, este FA é chamado de autômatos finitos não determinísticos.

Definição formal de NFA:

O NFA também possui cinco estados iguais ao DFA, mas com funções de transição diferentes, conforme mostrado a seguir:

 &#x3B4;: Q x &#x2211; &#x2192;2<sup>Q</sup> 

onde,

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Representação gráfica de um NFA

Um NFA pode ser representado por dígrafos chamados diagrama de estado. No qual:

1. O estado é representado por vértices.
2. O arco rotulado com um caractere de entrada mostra as transições.
3. O estado inicial está marcado com uma seta.
4. O estado final é indicado pelo círculo duplo.

Exemplo 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

Solução:

Diagrama de transição:

Tabela de Transição:

No diagrama acima, podemos ver que quando o estado atual é q0, na entrada 0, o próximo estado será q0 ou q1, e em 1 entrada o próximo estado será q1. Quando o estado atual é q1, na entrada 0 o próximo estado será q2 e na entrada 1, o próximo estado será q0. Quando o estado atual é q2, na entrada 0 o próximo estado é q2, e na entrada 1 o próximo estado será q1 ou q2.

Exemplo 2:

NFA com ∑ = {0, 1} aceita todas as strings com 01.

Solução:

Tabela de Transição:

Exemplo 3:

NFA com ∑ = {0, 1} e aceita todas as strings de comprimento pelo menos 2.

Solução:

Tabela de Transição: