Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
Par - Eliminer les états qui n’ont pas un chemin
Minimiser un Réduire le à partir de l’état initial
AFD nombre d’états - Fusionner les états reconnaissant le même
langage.
Pour
- Réduire le temps de reconnaissance
- Réduire l’espace mémoire utilisé pour sauvegarder l’AFD
78
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
Définition 1: Un état est dit inaccessible s’il n’existe
aucun chemin permettant de l’atteindre à partir de l’état
initial.
79
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
80
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
81
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
82
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Définition 2: Deux états qi et qj sont dits β-équivalents s’ils permettent
d’atteindre les états finaux en utilisant les mêmes mots (pour tout mot x V*,
δ(qi,x) F si et seulement si δ(qj,x) F). On écrit alors : qiβqj.
Remarques:
1-La relation R (R= β-équivalence) est une relation d’équivalence car elle est:
-Réflexive (pRp), p Q
-Symétrique (pRq qRp), p,q Q
-Transitive (pRq et qRq’ pRq’). p,q,q’ Q
2- Le nombre de classes d’équivalence de la relation β-équivalence est égal au
nombre des états de l’automate minimal car les états de chaque classe
d’équivalence reconnaissent le même langage (ils seront fusionnés).
83
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
1- Faire deux classes: A contenant les états finaux et B contenant les états non finaux;
2- S’il existe un symbole x et deux états qi et qj d’une même classe tel que δ(qi, x) et
δ(qj, x) n’appartiennent pas à la même classe, alors créer une nouvelle classe et
séparer qi et qj. On laisse dans la même classe tous les états qui donnent un état
d’arrivée dans la même classe;
3- Recommencer l’étape 2 jusqu’à ce qu’il n’y ait plus de classes à séparer;
Exemple:
84
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Exemple:
85
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Exemple:
86
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Exemple:
87
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Exemple:
88
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe d’équivalence:
Exemple:
89
Expression régulière et automates finis
Automates finis
Minimisation d’un AFD
2- Regrouper les états appartenant à la même classe
d’équivalence:
Exemple: même exemple avec autre méthode
Etat a b 1- A={1,2} , B={3,4,5,6}
*1 2 5 2- δ(3,b)=2∈A , δ(4,b)=3∈B, donc il faut séparer 4 (ou 3) du reste de
Etat a b
la classe B. Alors , on crée une classe C contenant l’état 4 (ou 3).
*2 2 4 *A A C
3- δ(3,b)=2∈A, δ(5,b)=6∈B, donc il faut séparer 5 de la classe B. On
3 3 2 peut mettre 5 dans la classe C (si C={4}) car δ(5,a)=4∈C et B B A
4 5 3 δ(4,a)=5∈C et δ(5,b)=6∈B et δ(4,b)=3∈B. Donc B={3,6} et C={4,5}. C C B
5 4 6 4- Aucun autre changement n’est possible, alors on arrête
l’algorithme. L’automate minimal est donc contient les trois états A
6 6 1
(état initial et final), B et C.
90
Expression régulière et automates
finis
Exercice
Minimiser l’AFD suivant:
91
Correction
A= {q5} et B={q0;q1;q2;q3 ;q4}
On a δ(q0 ,b)=q3 B et δ(q2 ,b)=q5 A alors il faut séparer q0 ou q2
du reste de la classe B donc on crée une classe contenant l’état q2.
Donc: A= {q5} et B={q0;q1;q3;q4} et C={q2}.
δ(q0 ,b)=q3 B et δ(q4 ,b)=q5 A on peut ajouter q4 dans la classe
C (car δ(q2,a)=q2 C et δ(q4,a)=q4 C et δ(q2 ,b)=q5 A et
δ(q4,b)=q5 A). Donc: A= {q5} et B={q0;q1;q3 } et C={q2;q4}.
δ(q0 ,b)=q3 B et δ(q1 ,b)=q2 C il faut séparer q0 ou q1 et on
crée une classe D contenant q1.
Donc: A= {q5} et B={q0;q3 } et C={q2;q4}.et D={q1}.
δ(q0 ,b)=q3 B et δ(q3 ,b)=q4 C on peut ajouter q3 à D car (car
δ(q1,a)=q1 D et δ(q3,a)=q3 D et δ(q1,b)=q2 C et
δ(q3,b)=q4 C). Donc: A= {q5} et B={q0} et C={q2;q4} et
D={q1;q3}.
92
Correction
NB: Utiliser la méthode des tableaux et comparer les 2
méthodes.
93
Expression régulière et automates finis
Exercice: Déterminer et minimiser l’automate suivant:
94
