Epsilon transition

En informatique théorique, et notamment en théorie des automates, une epsilon transition, notée aussi ε-transition et appelée également transition spontanée permet à un automate de changer d'état ou de configuration spontanément, sans consommer un symbole d'entrée. De telles transitions sont définies pour de nombreux modèles d'automate, et des algorithmes d'élimination existent ou pas selon les modèles.

Trois cas importants

Des cas particuliers importants sont notamment :

• automate fini
• automate à pile
• machine de Turing

Élimination des ε-transitions dans un automate fini

Un automate reconnaissant $a^{*}b^{*}$ avec une ε-transition de 1 à 2.

L'automate après élimination de la transition spontanée par fermeture arrière.

L'automate ci-contre est asynchrone : il possède une ε-transition de l'état 1 vers l'état 2. L'élimination des $\varepsilon$-transitions se fait par un algorithme de fermeture transitive. Appelons ε-chemin un chemin formé uniquement de ε-transitions. On peut alors procéder de deux façons différentes mais équivalentes, appelées fermeture avant et fermeture arrière par Sakarovitch, comme suit :

• (fermeture avant) Pour chaque transition d'un état $s$ à un état $t$ portant une lettre $a$ et pour chaque ε-chemin de $t$ à un état $u$, ajouter une transition de $s$ à $u$ d'étiquette $a$ ;
• (fermeture arrière) Pour chaque ε-chemin d'un état $s$ à un état $t$ et pour chaque transition de $t$ à un état $u$ portant une lettre $a$, ajouter une transition de $s$ à $u$ d'étiquette $a$ ;

Pour les états initiaux et terminaux, on complète par :

• (fermeture avant) Pour chaque ε-chemin d'un état $s$ initial à un état $t$, ajouter $t$ à l'ensemble des états initiaux.
• (fermeture arrière) Pour chaque ε-chemin d'un état $s$ à un état terminal $t$, ajouter $s$ à l'ensemble des états terminaux.

Bien entendu, on supprime les $\varepsilon$-transitions. Dans l'exemple de la figure, on ajoute la transition $1{\xrightarrow {b}}2$ dans la première étape en fermeture arrière, et on déclare que $1$ est état final dans la deuxième étape. Si on opère par fermeture avant, on ajoute la transition $1{\xrightarrow {a}}2$ et on déclare $2$ comme état initial.

La complexité en temps est celle du calcul d'une fermeture transitive, puisque l’on détermine les ε-chemins.

ε-règles dans un automate à pile

Une transition spontanée se produit dans un automate à pile en présence d'une ε-règle, c'est-à-dire d'une règle qui ne consomme pas de lettre d'entrée. Ces automates sont appelées automate en temps réel. On peut montrer que tout langage algébrique peut être reconnu par un automate à pile en temps réel et ne possédant qu'un seul état.

En revanche, tout langage algébrique déterministe ne peut pas être reconnu par un automate à pile déterministe en temps réel.

Dans les machines de Turing

La notion de ε-transition n’apparaît pas explicitement : elle est comprise dans le comportement qui consiste à ne pas modifier le symbole lu sur la bande. La règle de transition stipule donc que la lettre « écrite » est la même que la lettre « lue ».

Bibliographie

• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5) — Traduction anglaise avec corrections : (en) Elements of Automata Theory, Cambridge, Cambridge University Press, 2009, 758 p. (ISBN 978-0-521-84425-3)
• Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3540604204), p. 111--174