Sur la complexité moyenne de l'algorithme de Moore
47
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
47
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Sur la complexité moyenne de
1l’algorithme de Moore
Frédérique Bassino Julien David Cyril Nicaud
ALEA 2009
1STACS’09
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Automate déterministe complet
Un automate déterministe completA est
◮ un graphe fini orienté
◮ dont les transitions (ou arêtes) sont étiquetées sur un
alphabet fini
◮ avec un ensemble F d’états (ou sommets) terminaux
◮ un unique état initial.
◮ pour tout état p et pour toute lettre a de l’alphabet, il existe
exactement une transition sortant de p étiquettée par a.
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Un automate est accessible si
◮ pour tout état de l’automate, il existe un chemin partant de
l’état initial et passant par cet état.
Le langage reconnu par un automate est l’ensemble des
étiquettes des chemins allant d’un état initial à un état terminal.
Les langages rationnels sont les langages reconnus par un
automate fini.
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Automate
a,b
◮ Alphabet de l’automate :
A ={a, b}
◮ État initial : 14 a,b
◮ Ensemble des étatsb a terminaux : F ={1, 3}
a b
1 2 3
Frédérique Bassino, Julien David, Cyril Nicaud ALEA ...
Voir
Sur la complexité moyenne de
1l’algorithme de Moore
Frédérique Bassino Julien David Cyril Nicaud
ALEA 2009
1STACS’09
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Automate déterministe complet
Un automate déterministe completA est
◮ un graphe fini orienté
◮ dont les transitions (ou arêtes) sont étiquetées sur un
alphabet fini
◮ avec un ensemble F d’états (ou sommets) terminaux
◮ un unique état initial.
◮ pour tout état p et pour toute lettre a de l’alphabet, il existe
exactement une transition sortant de p étiquettée par a.
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Un automate est accessible si
◮ pour tout état de l’automate, il existe un chemin partant de
l’état initial et passant par cet état.
Le langage reconnu par un automate est l’ensemble des
étiquettes des chemins allant d’un état initial à un état terminal.
Les langages rationnels sont les langages reconnus par un
automate fini.
Frédérique Bassino, Julien David, Cyril Nicaud ALEA 2009 Algorithme de Moore La borne supérieure Le cas des automates unaires Conclusion
Automate
a,b
◮ Alphabet de l’automate :
A ={a, b}
◮ État initial : 14 a,b
◮ Ensemble des étatsb a terminaux : F ={1, 3}
a b
1 2 3
Frédérique Bassino, Julien David, Cyril Nicaud ALEA ...
1STACS'09 Frédérique Bassino, Julien David, Cyril Nicaud
Sur la complexité moyenne de l'algorithme de Moore1
Cyril Nicaud
Frédérique BassinoJulien David
ALEA 2009
ALEA 2009
Automate déterministe complet
Unautomate déterministe completAest ◮un graphe ni orienté ◮dont les transitions (ou arêtes) sont étiquetées sur un alphabet ni ◮avec un ensembleFd'états (ou sommets) terminaux ◮un unique état initial. ◮pour tout étatpet pour toute lettreade l'alphabet, il existe exactement une transition sortant depétiquettée para.
ALEA 2009
Frédérique Bassino, Julien David, Cyril Nicaud
ALEA 2009
Frédérique Bassino, Julien David, Cyril Nicaud
Lelangage reconnupar un automate est l'ensemble des étiquettes des chemins allant d'un état initial à un état terminal. Leslangages rationnelssont les langages reconnus par un automate ni.
Un automate estaccessiblesi ◮pour tout état de l'automate, il existe un chemin partant de l'état initial et passant par cet état.
irueusépacdsereLMoormedeorneeLabhtiroglAoCseulcnnoisauesmatosuteirna
a,b
4 a 2
b a
1
b
a,b 3
◮Alphabet de l'automate : A={ab} ◮État initial : 1 ◮Ensemble des états terminaux :F={13}
C,ryliiNacduLAAE
◮Pour tout langage rationnel, il n'y a pas d'unicité de l'automate reconnaissant ce langage.
ALEA 2009
◮La plupart des algorithmes de minimisation d'automates calculent la relation d'équivalence de Myhill-Nerode entre les états an de fusionner les états équivalents.
◮rationnel, il existe un unique automatePour tout langage déterministe accessible complet reconnaissant ce langage, tel que le nombre d'états soit minimal. On le nommeautomate minimal
Automate minimal
Frédérique Bassino, Julien David, Cyril Nicaud
iousnsCreclonureLecasesupérietasenuiaedastumoitorlgAnrobaLerooMedemh
Frédérique Bassino, Julien David, Cyril Nicaud
Automate minimal
ALEA 2009
◮Pour tout langage rationnel, il n'y a pas d'unicité de l'automate reconnaissant ce langage.
◮Pour tout langage rationnel, il existe un unique automate déterministe accessible complet reconnaissant ce langage, tel que le nombre d'états soit minimal. On le nommeautomate minimal
◮La plupart des algorithmes de minimisation d'automates calculent la relation d'équivalence de Myhill-Nerode entre les états an de fusionner les états équivalents.
ALEA 2009
◮La plupart des algorithmes de minimisation d'automates calculent la relation d'équivalence de Myhill-Nerode entre les états an de fusionner les états équivalents.
◮Pour tout langage rationnel, il existe un unique automate déterministe accessible complet reconnaissant ce langage, tel que le nombre d'états soit minimal. On le nommeautomate minimal
Automate minimal
Frédérique Bassino, Julien David, Cyril Nicaud
◮Pour tout langage rationnel, il n'y a pas d'unicité de l'automate reconnaissant ce langage.
edhmitorlgAncloniousianuCsermotusetaecasdesaérieureLobnrsepuMeooeraL
◮La complexité moyenne de l'algorithme de Moore est O(nlogn) ◮optimale pour le cas des automatesCette majoration est unaires.
Résultats principaux
Complexité dans le pire cas
◮Moore (1956) :O(n2) ◮Hopcroft (1971) :O(nlogn)
Frédérique Bassino, Julien David, Cyril Nicaud
ALEA 2009
reooboLahmiteMedrueiceLesenrrépuomatesunasdesautlcsuoiniaerCsno
Bibliothèque en C++, permettant d'engendrer aléatoirement et exhaustivement des automates déterministes accessibles.
Hopcroft FILO Moore
009NiD,udca0720Ra]2ERno[LAGssaB,onisunairesConclusieLacdsseuaotametsuneorabreeuripéemhtirogLerooMedAl 008009 00 001000Nombre d'etats 0000002003 04 0 5000 00006000 7510 1.02. 52.0 0.350.3 0 1 0.4 00.5 .0 0ybrartaLitomaivstauxhdEanomnduArofsrotareneGe
Frédérique Bassino, Julien David, Cyril Nicaud
ALEA 2009
p∼q⇐⇒les mots reconnus en prenantpetqcomme états initiaux sont les mêmes.
Partition de Myhill-Nerode
p∼iq⇐⇒les mots de longueur≤ireconnus en prenant petqcomme états initiaux sont les mêmes.
∼iest une partition de l'ensemble des états :
AhmitorlgreooeMedonsCusclunesreainoiupérieurLabornesastumotaLecesaed
ALEA 2009
p∼q⇐⇒les mots reconnus en prenantpetqcomme états initiaux sont les mêmes.
∼iest une partition de l'ensemble des états :
Frédérique Bassino, Julien David, Cyril Nicaud
Partition de Myhill-Nerode
p∼iq⇐⇒les mots de longueur≤ireconnus en prenant petqcomme états initiaux sont les mêmes.
AlthmegoriLerooMedusenrobareeuripéessdcaLeuaotametusanriseConclusion
