Automate transposé

En théorie des automates, l'automate transposé d'un automate fini ${\mathcal {A}}$ , noté ${\mathcal {A}}^{R}$ , est un autre automate fini, qui reconnaît les miroirs des mots reconnus par ${\mathcal {A}}$ . Par exemple si ${\mathcal {A}}$ reconnaît le mot aaaababa, alors ${\mathcal {A}}^{R}$ reconnaît ababaaaa.

On parle aussi d'automate miroir. Une autre notation est ${\mathcal {A}}^{t}$ .

Définition formelle[modifier | modifier le code]

Soit un automate fini (déterministe ou non déterministe) ${\mathcal {A}}=(Q,{\mathcal {F}},I,T)$ où $I$ et $T$ sont les états initiaux et terminaux et où ${\mathcal {F}}$ est l'ensemble des transitions.

L'automate transposé^[1] de ${\mathcal {A}}$ est l'automate obtenu en inversant le sens des transitions, et en échangeant les états initiaux avec les états terminaux. Formellement, c'est l'automate ${\mathcal {A}}^{R}$ .

{\mathcal {A}}^{R}=(Q,{\mathcal {F}}^{R},T,I)

,

où ${\mathcal {F}}^{R}=\{(p,a,q)\mid (q,a,p)\in {\mathcal {F}}\}$ .

Propriété et utilisations[modifier | modifier le code]

Le langage reconnu par l'automate transposé est formé des images miroir des mots reconnus par l’automate de départ.

En général, l'automate transposé n'est pas déterministe, mais la déterminisation de l'automate donne un automate déterministe minimal.

L'automate transposé est notamment utilisé dans l'algorithme de Brzozowski pour la minimisation d'un automate fini déterministe^[2].

Voir aussi[modifier | modifier le code]

graphe transposé, la notion analogue pour les graphes orientés.

Notes et références[modifier | modifier le code]

↑ Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5, zbMATH 1188.68177), p64.
↑ Jean Berstel, Luc Boasson, Olivier Carton et Isabelle Fagnot, « Minimization of Automata », dans Automata: from Mathematics to Applications, European Mathematical Society, 2010 (arXiv 1010.5318)

Portail de l'informatique théorique

[1] Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5, zbMATH 1188.68177), p64.

[2] Jean Berstel, Luc Boasson, Olivier Carton et Isabelle Fagnot, « Minimization of Automata », dans Automata: from Mathematics to Applications, European Mathematical Society, 2010 (arXiv 1010.5318)

[1]

[2]

v · m Automates finis et langages réguliers
Articles généraux	Théorie des automates Automate fini Machine abstraite
Automates finis	Automate fini déterministe Automate fini inambigu Automate fini non déterministe Construction par sous-ensembles Automate sur les mots infinis
Automates finis particuliers	Automate alternant Automate bidirectionnel Automate pondéré Automate probabiliste Automate quantique Automate temporisé Automate de Büchi Automate de Muller Modèle de Markov caché Système de transition d'états Structure de Kripke Machine à états abstraits Machine de Mealy Machine de Moore Transducteur fini Automate séquentiel
Langages réguliers	Langage rationnel Langage sans étoile Langage local Langage congruentiel Langage stochastique Lemme de l'étoile Lemme d'Arden ω-langage rationnel
Des automates aux langages	Expression régulière Algorithme de Conway Algorithme de McNaughton et Yamada Méthode de Brzozowski et McCluskey
Des langages aux automates	Dérivée de Brzozowski Algorithme de Thompson Construction de Glushkov Complexité en états
Minimisation	Théorème de Myhill-Nerode Équivalence de Nerode Minimisation d'un automate fini déterministe Algorithme de Moore Algorithme de Brzozowski Algorithme de Hopcroft
Équivalences	Théorème de Kleene Étoile de Kleene Monoïde syntaxique Théorème des variétés d'Eilenberg