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 .

Formalmente, um AFN é definido por uma 5-tupla , onde:

• : conjunto finito de estados;
• : alfabeto de entrada;
• : função de transição, agora definida como (retorna um conjunto de estados possíveis);
• : estado inicial;
• : conjunto de estados finais.

Uma cadeia é aceita por um AFN se existe pelo menos um caminho a partir de que, ao processar , termina em um estado de .

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:
• Transições:
  • , ,
  • ,
  • , .
• inicial, .
• 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:
• Transições:
  • , ,
  • , ,
  • , .
• inicial, .

Referências §

---