Théorie des langages : Cours minimisation des automates finis déterministes
Télécharger PDFMinimisation des Automates Finis Déterministes
M. AdilKENZI
1Théorie des langagesPlan Introduction
Equivalence des états d’un automate fini déterministe Définitions
Algorithme de minimisation des automates finis déterministes
Illustration de l’algorithme de minimisation à travers un exemple
2Théorie des langages
Introduction
la minimisation d’un automate fini déterministe consiste à trouver un automate déterministe avec un nombre minimal d’états qui reconnait le même langage
Pour chaque automate d’états fini déterministes, nous pouvons trouver un automate fini déterministe ayant un minimum d’états
En réalité, l’automate d’états fin est unique : pour deux automates finis , nous pouvons trouver une méthode pour renommer les états. Ainsi les deux automates sont identiques. 3Théorie des langages
Introduction
Idée de base : 1.Trouver les états équivalents 1.Utilisation d’algorithme donné
2.L’automate minimal regroupe les états équivalents
4Théorie des langages
Définitions
Deux états p,qde A sont dits équivalentsssi
w* tq(p,w) est un état final (q,w) est un état final
Deux états p,qde A sont dits distingués si ils ne sont pas équivalents
1.w =, si p F q F alors p et q sont distinguables (non équivalents)
2.w , ((p,w)=r et (q,w)=s) ET (r et s sont distinguables) alors p et q sont distinguables
5Théorie des langages
Algorithme de minimisation
1.Créer un tableau associé à l’automate à minimiser 2.Marquer les paires d’états (p, q) pour chaque p
F et q F
3.Pour chaque paire non marquée p, q et chaque symbole a :1.Soit r = (p,a), s = (q,a).
2.Si (r,s) est non marquée ajouter (p, q) à la liste des paires dépendantes de (r, s) 3.Si non, marquer (p,q) ainsi que la liste des paires dépendantes
6Théorie des langagesa dcbehf g1 01 11 00 00 00 11 11 bc de fg habcdefg 1.Création d’un tableau associé à l’automate à minimiser :
initialement , toutes les paires ont non marquées Exemple0 7Théorie des langagesadcb ehfg 10 11 10 00 00 01 11 1b cd ef gh abcdefg
2. Marquer les paires d’états (p, q) pour chaque pF et q F
8Théorie des langagesadcb ehfg 10 11 10 00 00 01 11 1b cd ef gh abcdefg
δ(b,0) ? δ(a,0)
δ(b,1) ? δ(a,1)0 9Théorie des langages
3. Pour chaque paire non marquée & symbole . . .adcb ehfg 10 11 10 00 00 01 11 1b cd ef gh abcdefg
g ? b
c ? f
possibleNon δ(b,0) ? δ(a,0)
δ(b,1) ? δ(a,1)0 10Théorie des langages
3. Pour chaque paire non marquée & symbole . . .adcb ehfg 10 11 10 00 00 01 11 1b cd ef gh abcdefg
δ(d,0) ? δ(a,0)c ?b Non
δ(d,1) ? δ(a,1)g ?f possible
Marquer(d,a)0 11Théorie des langages
3. Pour chaque paire non marquée & symbole . . .adcb ehfg 10 11 10 00 00 01 11 1b cd ef gh abcdefg
δ(e,0) ? δ(a,0)
δ(e,1) ? δ(a,1)0 12Théorie des langages
3. Pour chaque paire non marquée & symbole . . .adcb ehfg 10 11 10 00 00 01 11 1b cd ef gh (a,e)abcdefg h ? b
f ? f
possible.oui 0
13Théorie des langages
3. Pour chaque paire non marquée & symbole . . .b cd ef gh (a,e)abcdefg δ(f,0) ? δ(a,0)c ?b Non
δ(f,1) ? δ(a,1)g ?f possibleadcb ehfg 10 11 10 00 00 01 11 10 14Théorie des langages
3. Pour chaque paire non marquée & symbole . . .b cd ef gh (a,e)abcdefg δ(g,0) ? δ(a,0)g ?b possible
δ(g,1) ? δ(a,1)e ?f possibleadcb ehfg 10 11 10 00 00 01 11 1
3. Pour chaque paire non marquée & symbole . . .0 15Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(g,0) ? δ(a,0)g ?b possible
δ(g,1) ? δ(a,1)e ?f possibleadcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
16Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(h,0) ? δ(a,0)g ?b possible
δ(h,1) ? δ(a,1)c ?f Non
Marquer(h,a)adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
17Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(d,0) ? δ(b,0)c ?g Non
δ(d,1) ? δ(b,1)g ?c Non
marquer(d,b)adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
18Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(e,0) ? δ(b,0)h ?g possible
δ(e,1) ? δ(b,1)f ?c Non
marquer(e,b)adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
19Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(f,0) ? δ(b,0)c ?g Non
δ(f,1) ? δ(b,1)g ?c Non
Marquer(b,f)adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
20Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(g,0) ? δ(b,0)g ?g oui
δ(g,1) ? δ(b,1)e ?c Non
marquer(g,b) –Récursivement,
marquer (g,a).adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
21Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(g,0) ? δ(b,0)g ?g Yes
δ(g,1) ? δ(b,1)e ?c No
marquer (g,b) –Recursivement,
marquer (g,a).adcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
22Théorie des langagesb cd ef (g,a)g (g,a)h (a,e)abcdefg δ(h,0) ? δ(b,0)g ?g oui
δ(h,1) ? δ(b,1)c ?c oui
Ne pas marqueradcb ehfg 10 11 10 00 00 01 11 10 3. Pour chaque paire non marquée & symbole . . .
23Théorie des langagesadcb ehfg 10 11 10 00 00 01 11 1b cd ef gh (a,e)abcdefg 0
3. Pour chaque paire non marquée & symbole . . .
24Théorie des langages
Minimisation d’un DFA
L’automate minimal regroupe les états équivalentsb cd ef gh abcdefg
{a,e}, {b,h}, {c}, {df}, {g}
a e
b h
d f
25Théorie des langagesaebh gdfc 01 11 11 00 00 Automate minimal
26Théorie des langagesadcb ehfg 10 11 10 00 00 01 11 1b cd ef gh (a,e)abcdefg aec bhdf g1 011 00 00 11 {a,e}, {b,h}, {c}, {df}, {g}
27Théorie des langages
Exemple 1
28Théorie des langages
Questions?
29Théorie des langages