Autômato Finito Não Determinístico (AFND)

---

Um autômato finito não-determinístico (AFN) é um modelo computacional usado para reconhecer linguagens regulares, assim como o autômato finito determinístico (AFD).

Diferentemente do AFD, o AFN introduz a ideia de não-determinismo, permitindo que o autômato tenha escolhas ambíguas durante a execução. Isso significa que, para uma mesma entrada em um dado estado, o AFN pode seguir múltiplos caminhos possíveis, incluindo transições espontâneas (sem consumir símbolos), chamadas de $ϵ-transi\stackrel{\backslash c}{c}\tilde{o}es$.

Formalmente, um AFN é definido por uma 5-tupla $N=(Q,\Sigma ,\delta ,q_0,F)$, onde:

• $Q$: conjunto finito de estados;
• $\Sigma$: alfabeto de entrada;
• $\delta$: função de transição, agora definida como $\delta :Q\times (\Sigma \cup \{ϵ\})\to 2^Q$ (retorna um conjunto de estados possíveis);
• $q_0$: estado inicial;
• $F$: conjunto de estados finais.

Uma cadeia $w\in {\Sigma }^{\ast }$ é aceita por um AFN se existe pelo menos um caminho a partir de $q_0$ que, ao processar $w$, termina em um estado de $F$.

NOTE

Essa flexibilidade torna o AFN mais intuitivo para modelar certos problemas, embora seja equivalente ao AFD em termos de poder expressivo (ambos reconhecem linguagens regulares) e também em termos de desempenho.

Exemplo

Considere a seguinte linguagem: Cadeias que terminam em “ab”.

AFN

stateDiagram-v2
    [*] --> q0
    q0 --> q0 : a, b
    q0 --> q1 : a
    q1 --> q2 : b
    q2 --> [*]

• Estados: $\{q_0,q_1,q_2\}$
• Transições:
  • $\delta (q_0,a)=\{q_0,q_1\}$, $\delta (q_0,b)=\{q_0\}$,
  • $\delta (q_1,b)=\{q_2\}$,
  • $\delta (q_2,a)=\varnothing$, $\delta (q_2,b)=\varnothing$.
• $q_0$ inicial, $F=\{q_2\}$.
• Compacto e intuitivo: “adivinha” quando começa o “ab”.

AFD

stateDiagram-v2
    [*] --> q0
    q0 --> q0 : b
    q0 --> q1 : a
    q1 --> q1 : a
    q1 --> q2 : b
    q2 --> q1 : a
    q2 --> q0 : b
    q2 --> [*]

• Estados: $\{q_0,q_1,q_2\}$
• Transições:
  • $\delta (q_0,a)=q_1$, $\delta (q_0,b)=q_0$,
  • $\delta (q_1,a)=q_1$, $\delta (q_1,b)=q_2$,
  • $\delta (q_2,a)=q_a$, $\delta (q_2,b)=q_0$.
• $q_0$ inicial, $F=\{q_{ab}\}$.

Referências

---