Duvidas? Tá perdido? Veja nossos poster anteriores. Prestem muita atenção a parti de agora. Procedimento para conversão de um AFN em AFD.
cadeirawSupondo o autômato

Sendo M o autômato ao lado, N tem 3 estados {1, 2, 3} e M1 terá todos os possíveis  subconjuntos de estados de M.

{{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2,3}, {1, 2, 3}}

O estado inicial é E({1}) = {1, 3} → conjunto de estados atingíveis a partir de 1 viajando ao longo de setas ε.
Os novos estados de aceitação são aqueles que contem o estado de aceitação de M → {{1}, {1, 2}, {1, 3}, {1, 2, 3}}

Representação da conversão de AFN para AFD.
Representação da conversão de AFN para AFD.

Podemos Simplificar essa máquina observando que nenhuma transição aponta para os estados {1} e {1, 2}.

Simplificação da conversão.
Simplificação da conversão.