Sur la complexité moyenne de l
47 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Sur la complexité moyenne de l'algorithme de Moore

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
47 pages
Français

Description

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 ...

Sujets

Informations

Publié par
Nombre de lectures 150
Langue Français

Exrait

AlgorithmedeMooeraLobnrsepuréeieLurasecsadeomutsetaianuCserlcnonusio
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
mhtiMedeerooobaLAorlgsaedastumotasenurnesupérieureLeconsCreainiouscl
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
AlgoedemhtirbaLerooMpésuneorLereeuriulcnnoisrianoCsematosutesdcaauesAutomatenosiul,JnDieidavFédéruqirsaBe2009
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
sautomateLecasdepuréeiruaLobnrsenionoCssulcnuseeriamhtiroglerooMedeA
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
orlgA
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
-vin.vlmrFrfrédéueiqssBao,inliJu2http://regal.uiv,dneaDNlciyCirLEA2audA
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
pq⇐⇒les mots reconnus en prenantpetqcomme états initiaux sont les mêmes.
Partition de Myhill-Nerode
piq⇐⇒les mots de longueurireconnus en prenant petqcomme états initiaux sont les mêmes.
iest une partition de l'ensemble des états :
AhmitorlgreooeMedonsCusclunesreainoiupérieurLabornesastumotaLecesaed
ALEA 2009
pq⇐⇒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
piq⇐⇒les mots de longueurireconnus en prenant petqcomme états initiaux sont les mêmes.
AlthmegoriLerooMedusenrobareeuripéessdcaLeuaotametusanriseConclusion
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents