Algoritmo de minimização de AFD
Considere o AFD M1 abaixo:
1. Remover estados não alcançáveis
Eliminar os estados não alcançáveis, ou seja, que não são possíveis de acessar a a partir do estado inicial
2. Construir a tabela de distinção
- Inicialmente, marque pares de estados como distintos se um é final e o outro não.
- Iterativamente, marque pares como distintos se, para algum símbolo
, suas transições levam a estados já marcados como distintos. - Pares não marcados são equivalentes.
3. Agrupar estados equivalentes
- Combine estados equivalentes em um único estado.
- Ajuste as transições e o conjunto de estados finais conforme os grupos.
4. Repetir o processo
- Repetir esse passo a partir dos conjuntos finais e não finais até que não tenhamos mais novas partições (classes de equivalência).