Autómato finito determinista
Last updated
Last updated
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:
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.
Que palavras são reconhecidas pelo autómato seguinte:
Todas as palavras terminadas em 11.
Como expressão regular: (0|1)*11
Que palavras são reconhecidas pelo autómato seguinte:
Todas as palavras com 1 ou 2 zeros.
Como expressão regular: 1* 01* 0?1*
Represente analiticamente o AFD:
