Sur la complexité moyenne de l'algorithme de Moore

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