Conversão de AFND em AFD
Last updated
Last updated
Como já foi referido um AFD é um AFND, mas o contrário não é necessariamente verdadeiro.
Nos AFD as transições são funções e as tabelas de transição são mais simples havendo sempre uma transição para no máximo um único estado.
Assim, em geral, a implementação de AFD é preferível à implementação de AFND.
É sempre possível converter um AFND num AFD.
Vamos ver um algoritmo genérico para esse efeito.
A ideia geral do algoritmo resulta da constatação de que num AFND as transições fazem-se de um subconjunto dos seus estados para outro subconjunto.
Assim podemos transformar um AFND num AFD tomando como estados os subconjuntos do AFND.
Com esta estratégia, para um AFND com n estados no pior caso podemos ter 2^n estados no AFD.
No entanto, em geral constata-se que o número de estados é da mesma ordem de grandeza.
O algoritmo assenta na construção, passo a passo, da tabela de transição para o AFD, partindo do AFND.
Considerando que: s é um qualquer estado do AFND, C é um conjunto de estados do AFND e a é um qualquer símbolo de entrada, então:
O estado inicial do AFD será o resultante da aplicação de e-closure ao estado inicial do AFND.
Os estados finais do AFD, serão todos os estados que contiverem pelo menos um estado final do AFND.
Como exemplo, vamos considerar o AFND seguinte:
Logo, vamos ter o seguinte AFD:
A AFND seguinte foi uma implementação (que, como veremos, resulta directamente da aplicação de um algoritmo) da expressão regular: (a|b)*abb
Este AFD pode ainda ser minimizado (os estados A e C são equivalentes):