Conversão de AFND em AFD

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):