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.

Referências §

---

Aula - Minimização de AFD