Minimização de Automatos

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 Hopcroft (1971). É baseado no refinamento de partição, no qual estados do AFD são particionados em grupos, de acordo com seu comportamento. Esses grupos representam classes de equivalência, pela qual todos dois estados da mesma partição são equivalentes se eles têm o mesmo comportamento para todas as sequências de entrada.
Isto é, para todo dois estados p_1 e p_2 que pertencem à mesma classe de equivalência da partição P, temos que para qualquer palavra de entrada w, ao seguir-se as transições determinadas por w partindo dos estados p_1 e p_2, ambos os estados serão levados a estados de aceitação, ou ambos a estados de rejeição, não deveria ser possível a w levar p_1 a um estado de aceitação e p_2 a um estado de rejeição, ou vice-versa. Definição
• O objetivo da minimização é gerar o autômato finito equivalente com o menor numero de estados possiveis, este é denominado de autômato finito determinístico mínimo ou simplismente autômato finito mínimo.
• O autômato finito mínimo é único, assim, dois autômatos distintos que aceitam a mesma linguagem, ao serem minimizados, geram o mesmo autômato finito mínimo, diferenciando eventualmente na identificação dos estados.

Definição
• Regras para a minimização de