Teoria da computação – Conversão AFN PARA AFD
Duvidas? Tá perdido? Veja nossos poster anteriores. Prestem muita atenção a parti de agora. Procedimento para conversão de um AFN em AFD.
Supondo 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.
Podemos Simplificar essa máquina observando que nenhuma transição aponta para os estados {1} e {1, 2}.
Simplificação da conversão.
