Deux contrôleurs différents peuvent trier exactement de la même façon. La minimisation le prouve en regroupant les états qu'aucun mot ne distingue.
L'automate à minimiser
Alphabet , état initial A, seul état acceptant D.
| Depuis | 0 | 1 |
|---|---|---|
A | B | C |
B | B | D |
C | B | D |
D | E | D |
E | B | D |
Objectif
Dérouler le raffinement de partition et compter ce qu'il reste.
Comment lire le résultat
L'algorithme sépare, il ne regroupe jamais. Il part de la partition la plus grossière qui soit défendable, acceptants d'un côté et non-acceptants de l'autre, puis coupe chaque fois qu'un symbole mène deux états d'une même classe dans des classes différentes. Ce symbole est la preuve qu'un mot distingue les deux états, et cette preuve est constructive : elle donne le mot.