CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Autômatos Finitos Não-Determinísticos

Quando falamos de autômatos finitos, significa que, quando uma máquina está em um dado estado e lê o próximo símbolo de entrada, sabemos qual será o próximo estado, ou seja, está determinado. Chamamos isso de computação determinística. Em uma máquina não-determinística, várias escolhas podem existir para o próximo estado em qualquer ponto. O não-determinismo pode ser visto como uma espécie de computação paralela na qual múltiplos e independentes "processos" ou "threads" podem estar rodando concorrentemente. Quando o AFN se divide para seguir as diversas escolhas, isso corresponde a um processo "bifurcar" em vários filhos, cada um procedendo separadamente. Se pelo menos um desses processos aceita, então a computação inteira aceita.

Como o não-determinismo é uma generalização de determinismo, todo AFD é automaticamente um autômato finito não-determinístico (AFN). Uma das principais diferenças dos AFNs para os AFDs são a presença de transições vazias ε e cada estado pode ter zero, uma ou várias transições saindo para cada símbolo do alfabeto.

Definição Formal

Um autômato finito não-determinístico é uma 5-upla (Q, Σ, δ, q0, F), onde:

• Q é um conjunto finito de estados do AF;
• Σ é o alfabeto;
• δ: Q x Σε→ P(Q) é a função de transição;
• q0 ∈ Q é o estado inicial; e
• F ⊆ Q é o conjunto de estados de aceitação (ou finais).

Perceba que a definição formal dos AFNs é similar ao dos AFDs, porém a função de transição muda. Nos AFNs, a função de transição toma um estado e um símbolo de entrada ou a cadeia vazia e produz o conjunto de próximos estados possíveis. P(Q) seria a coleção de todos os subconjuntos de Q, para qualquer conjunto Q.