Minimização de autômato finito determinístico - AFD
Um AFD reconhece palavras de uma única linguagem regular, denotada por , que é o conjunto de cadeias aceitas por .
Para uma mesma linguagem , podem existir diversos AFDs distintos que a reconhecem. Por exemplo, um AFD com 10 estados e outro com 5 estados podem aceitar exatamente a mesma linguagem.
O objetivo da minimização é encontrar um AFD equivalente (que reconhece a mesma linguagem) com o menor número possível de estados.
Eficiência Computacional
Em termos práticos, como na implementação de compiladores, é desejável que o AFD tenha o menor número possível de estados.
Menos estados implicam menor uso de memória e maior eficiência no processamento, além de ser mais fácil de implementar.
AFD Mínimo
Um AFD é dito mínimo para a linguagem se não existe outro AFD que reconheça com menos estados que .
O AFD mínimo é único (exceto por isomorfismos, ou seja, renomeação de estados).
Processo de Minimização
Para transformar um AFD qualquer em seu equivalente mínimo, seguimos dois passos principais:
Passo 1: Eliminação de Estados Não-Alcançáveis
Um estado é não-alcançável se não há caminho a partir do estado inicial até ele, independentemente da entrada.
NOTE
Esses estados não contribuem para o reconhecimento da linguagem e podem ser removidos.
Exemplo:
- Considere o AFD com , , e transições:
- , ,
- , ,
- não aparece em nenhuma transição.
- é não-alcançável e pode ser eliminado.
Passo 2: Identificação e Fusão de Estados Equivalentes
Dois estados e são equivalentes se, para qualquer entrada, levam ao mesmo comportamento de aceitação (ou seja, aceitam ou rejeitam as mesmas cadeias a partir deles).
Formalmente, e são equivalentes se, para toda cadeia :
- se e somente se , onde é a função de transição estendida.
NOTE
Substituímos cada grupo de estados equivalentes por um único estado representativo.
E denominamos que dois estados e não são equivalentes (distinguíveis) se a afirmação acima não for satisfeita.