AUTOMATES
MINIMISATION D’UN AUTOMATE
MINIMISER UN AUTOMATE
• La minimisation d’un automate consiste à réduire le nombre d’états et
de transitions d’un automate fini tout en conservant son
comportement.
• Cela permet d’obtenir un automate plus compact et plus simple, ce
qui facilite son analyse, sa compréhension et sa mise en œuvre.
• Ainsi le processus de minimisation d’un automate fini déterministe
(AFD) se déroule généralement en plusieurs étapes :
1. Identification des états accessibles:
• On commence par identifier les états accessibles, c’est-à-dire les états
qui peuvent être atteints à partir de l’état initial en suivant les
transitions de l’automate.
• Soit un exemple
• Automate initial :
• Etats : A ,B,C ; Alphabet : 0,1 ; Etat initial : A ; Etat final : C
• Transitions : (A,0,B) ; (A,1,C); (B,0,B) ; (B,1,C); (C,0,A) ; (C,1,C);
• En respectant cette étape on aura comme état accessible A et
comme états non accessibles B ,C.
2. Identification des états Co accessibles
• Ici, l’on identifie les états Co accessibles, c’est-à-dire les états qui
peuvent atteindre un état final en suivant les transitions de l’automate
• En respectant cette étape l’on aura à partir de l’automate défini plus
haut comme état Co accessible C et comme états non Co accessibles
A
Automate final réduit
• Etats : A , C
• Alphabet : 0,1
• Etat initial : A
• Etat final : C
• Transitions : (A,0,B) ; (A,1,C) ; (C,1,C)
[Link] des états équivalents
• Une fois les états accessibles et Co accessibles identifiés, on regroupe
les états équivalents en un seul état. Deux états sont équivalents s’ils
mènent aux mêmes états finaux pour tous les mots du langage
accepté par l’automate.
• En respectant cette étape on aura :
• Les états A et C ne sont pas équivalents, car ils ne mènent pas aux
mêmes états finaux pour tous les mots du langage. Donc suite à cette
étape l’automate n’aura subis aucun changement du fait de la non
équivalence entre les états
4.Réduction des transitions
• A ce niveau l’on simplifie l’automate en supprimant les transitions
redondantes et en fusionnant les transitions menant vers le même
état. On aura :
• Transition de C vers A avec 0 est redondant car l’état A est déjà
accessible depuis l’état initial.
• Transition de C vers C avec 1 est conservée car elle est nécessaire
pour atteindre l’état final C.
Automate
Après l’étape 1: Après l’étape 2 :
• Etats : A • Etats : A,C
• Alphabet : 0,1 • Alphabet : 0,1
• Etat initial : A • Etat initial : A
• Etat final : C • Etat final : C
• Transitions : (A,0,B) ; (A,1,C) • Transitions : (A,0,B) ; (A,1,C);
(C,0,A) ; (C,1,C)
