Autómato finito determinista

Um autómato finito determinista (AFD) é um caso especial de um AFND onde:

Não há transições com a palavra vazia (ε).
Para cada estado S e símbolo de entrada a existe no máximo uma transição de s anotada com a.

Num AFD completo, existe uma transição para todos os símbolos do alfabeto.

Um diagrama de transição para um AFD que reconhece a expressão regular (a | b)*abb é o seguinte:

Autómato finito determinista: tabela de transição

Se estivermos a representar um AFD com uma tabela de transição, então cada entrada será um único estado (pelo que deixa de ser necessário representá-lo como conjunto):

Enquanto um AFND é uma representação abstracta dum algoritmo para reconhecer expressões regulares, o AFD é um algoritmo simples, concreto e muito eficiente para o mesmo fim.

Felizmente é possível converter um AFND num AFD que reconhece a mesmo linguagem regular.