Minimização de
Autômatos
Alexsander, Fernando, Marcelo e Kelvin

Como Surgiu
• O algoritmo de Moore para minimização de AFD foi proposto em (1956). Ele mantém uma partição que inicia separando os estados de aceitação dos estados de rejeição, e repetidamente refina a partição até que nenhum outro refinamento possa ser efetuado. Em cada passo, ele substitui a partição atual com o refinamento mais grosso das s + 1 partições, das quais uma é a atual e as outras são as préimagens da partição atual sob as funções de transição para cada um dos símbolos de entrada. O algoritmo termina quando essa substituição não muda a partição atual.

Como Surgiu
• Um algoritmo para mesclar estados indistinguíveis do AFD, elaborado por …exibir mais conteúdo…

• Obs: no proximo passo(passo4) quando os conjuntos não forem equivalentes, separa-se o conjunto em estados simples novamente.
• Passo4, verificar novamente se os conjuntos que restaram são equivalentes fazendo uma tabela com suas saidas:

• Como eles são equivalentes, podemos junta-los, então tudo que for q2 ou q3 fica=> M

• Passo 5 : criar a função de transição original e depois substituir o que for possivel e eliminar na transição as linhas que forem repetidas.

AFD Resultante

• Função de transição restante:

• Ultimo passo: Montar o AFD a partir da função de transição.

Exemplo 2
• Bom primeiro precisamos fazer a comparação dos estados, se são finais ou não finais, e se percorrem os mesmos tipos de estados. Exemplo 2
• Como o estado Q4 e Q3 é um estado final e diferente dos demais ele já pode ser marcado descartando-o como equivalente com qualquer outro estado não final.

Exemplo 2

• Agora fazemos a comparação entre os estados na tabela, vamos começar com o (Q0, Q1).
• Q0 lendo (a) vai para Q1(estado não final)
• Q1 lendo (a) vai para Q3(estado final)
• Não são equivalentes pois um é estado não final e o outro é o estado final.
• Obs.: Ele tem que estar lendo a mesma letra, e indo para um mesmo tipo de estado.

Exemplo 2
•
•
•
•

Comparemos agora (Q0, Q2)
Q0 lendo (a) vai para Q1(estado não final)