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

Un automate A.

Le transposé de l'automate A.

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

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

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

Notes et références

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

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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)