Minimisation d’un automate

Minimiser un automate, c’est trouver un automate équivalent qui possède le plus petit nombre d’états possible. Même un automate sans état inutile peut encore être simplifié.

Exemple

Prenons cet automate :

Il n’accepte que les mots 01 et 11. Il est pourtant évident qu’il existe un automate plus simple, à trois états, qui accepte le même langage. Les états q₁ et q₂ peuvent être fusionnés en un nouvel état {q₁ ; q₂} ; les transitions qui menaient à q₁ ou à q₂ mèneront au nouvel état, et de même pour les transitions qui partaient de q₁ et q₂. On obtient cet automate :

Cet automate accepte manifestement le même langage que le précédent et il a moins d’états.

Équivalence d’états

Soit un automate A = (Q ; Σ ; δ ; q₀ ; F). On définit le langage d’un état q ∈ Q, noté L(q), par

$L (q) = L ((Q; Σ; δ; q; F))$

C’est-à-dire que l’on remplace l’état initial q₀ de l’automate A par q et que l’on détermine le langage accepté par cet automate. Autrement dit, le langage L(q) contient tous les mots w tels que, dans l’automate A, on arrive de l’état q à un état final en lisant le mot w. Si l’on revient à l’automate précédent, on a L(q₁) = {1}.

On dit que deux états distincts q₁ et q₂ sont équivalents si

$L (q_{1}) = L (q_{2})$

Qu’est-ce que cela signifie ? Si les états q₁, q₂ sont équivalents, alors, quand on en fait des états initiaux de l’automate, ils engendrent le même langage. Autrement dit : si l’automate arrive dans la configuration (q₁ ; w) et dans la configuration (q₂ ; w), il doit, dans les deux cas, soit accepter, soit rejeter.

Revenons à l’automate précédent : les états q₁ et q₂ sont équivalents, car quand on est dans l’état q₁, on ne peut accepter le mot d’entrée que si la partie non lue du mot est égale à 1. Il en va de même dans l’état q₂.

Minimiser un automate consiste donc à trouver les états équivalents et à les supprimer en les fusionnant en un nouvel état, comme nous l’avons fait dans l’exemple ci-dessus.

Comment trouver les états équivalents

Quels états ne sont certainement pas équivalents ? Un état final et un état non final ne sont sûrement pas équivalents, car le langage d’un état final est différent de celui d’un état non final : un état final accepte à coup sûr le mot ε, un état non final ne l’accepte pas. Montrons la méthode directement sur un exemple. Prenons cet automate :

On commence par créer deux ensembles d’états

$\begin{array}{rcl} S_{1} & = & F = {q_{3}; q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}; q_{1}; q_{2}; q_{4}; q_{5}} . \end{array}$

Nous créons maintenant la table de transition en gardant l’information sur les classes S₁ et S₂ :

$\begin{array}{ccccc} classe & état & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Modifions maintenant la table : au lieu d’écrire directement dans quels états on arrive pour chaque lettre, on note seulement la classe dans laquelle on arrive. Par exemple, de l’état q₃ avec 0, on arrive à l’état q₅, qui est dans la classe S₂. Au lieu de q₅, on écrit donc S₂ dans la table :

$\begin{array}{ccccc} classe & état & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Nous subdivisons maintenant les deux classes. On met dans une même classe les états qui vont dans les mêmes classes pour toutes les lettres. Par exemple, les états q₃ et q₆ ne seront pas dans la même classe, car ni avec 0 ni avec 1 ils ne vont dans la même classe. En revanche, les états q₁ et q₂ seront dans la même classe, car aucun des deux n’a de transition pour 0 et tous deux vont dans la classe S₁ pour 1. Nous créons ainsi de nouvelles classes :

$\begin{array}{ccccc} classe & état & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Dans chaque classe, les transitions sont les mêmes. Nous nommons les classes ainsi obtenues et déterminons de nouveau dans laquelle de ces nouvelles classes les états arrivent :

$\begin{array}{ccccc} classe & état & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

On procède alors à un nouveau partage des classes. Mais on voit qu’on ne peut plus en faire d’autre, on obtiendrait les mêmes classes : en effet, les états q₁ et q₂ ont certes les mêmes transitions vers les classes, mais ils sont déjà dans la même classe et il n’y a pas d’autre état dans la classe S₄. L’algorithme de recherche des états équivalents est terminé. Dans chaque classe, il suffit de choisir un état, on supprime les autres et toutes les transitions qui menaient aux états supprimés mèneront à l’état choisi.

On peut ainsi choisir que notre nouvel automate aura les états q₃, q₆, q₀, q₁, q₄ et que l’on supprime les états q₂ et q₅. Toutes les transitions qui menaient à q₂ mèneront maintenant à q₁ et toutes celles qui menaient à q₅ mèneront à q₄ :

Méthode de minimisation d’un automate

On supprime les états inaccessibles,
on supprime les états inutiles,
on supprime les états équivalents.

Sources

Chapitres: États inaccessibles, États inutiles, Minimisation d’un automate

« Précédent: États inutiles

Suivant: Propriétés de clôture des langages réguliers »