Voir la source de Epsilon transition

{{Voir homonymie | epsilon (homonymie)}}
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'''<ref>Terminologie de {{harvsp|Sakarovitch|2003}} par exemple.</ref>  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 ==
{{loupe|Automate fini non déterministe#Extensions des automates finis (dont epsilon transitions)}}
[[Fichier:Automate-asynchrone.png|thumb|Un automate reconnaissant <math>a^*b^*</math> avec une ε-transition de 1 à 2.]]
[[Fichier:Automate-synchronise.png|thumb|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 <math>\varepsilon</math>-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<ref>{{harvsp|Sakarovitch|2003}}.</ref>,  comme suit :
* (fermeture avant) Pour chaque transition d'un état  <math>s</math> à un état <math>t</math> portant une lettre <math>a</math> et pour chaque ε-chemin de  <math>t</math> à un état <math>u</math>, ajouter une transition de <math>s</math> à <math>u</math> d'étiquette <math>a</math> ;
* (fermeture arrière) Pour chaque ε-chemin d'un état <math>s</math> à un état <math>t</math> et pour chaque transition de <math>t</math> à un état <math>u</math> portant une lettre <math>a</math>, ajouter une transition de <math>s</math> à <math>u</math> d'étiquette <math>a</math> ;
Pour les états initiaux et terminaux, on complète par :
* (fermeture avant) Pour chaque ε-chemin d'un état <math>s</math> initial à un état <math>t</math>, ajouter <math>t</math> à l'ensemble des états initiaux.
* (fermeture arrière) Pour chaque ε-chemin d'un état <math>s</math> à un état terminal <math>t</math>, ajouter <math>s</math> à l'ensemble des états terminaux.
Bien entendu, on supprime les <math>\varepsilon</math>-transitions.
Dans l'exemple de la figure, on ajoute la transition <math>1\xrightarrow b 2</math> dans la première étape en fermeture arrière, et on déclare que <math>1</math> est état final dans la deuxième étape. Si on opère par fermeture avant, on ajoute la transition <math>1\xrightarrow a 2</math> et on déclare <math>2</math> 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 à pile#Automate en temps réel | automate en temps réel]]''.  On peut montrer<ref>{{harvsp|Autebert|Berstel|Boasson|1997|p=}}.</ref> 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 ». 

== Notes et références ==
{{Références}}

== Bibliographie ==
* {{Introduction to Automata Theory, Languages, and Computation}}
* {{Ouvrage| auteur1=Jacques Sakarovitch| titre=Éléments de théorie des automates| éditeur=Vuibert| année=2003| pages totales=816| isbn=978-2-7117-4807-5}} {{commentaire biblio SRL | Traduction anglaise avec corrections : {{Ouvrage|langue=en|titre=Elements of Automata Theory|éditeur=Cambridge University Press|lieu=Cambridge|année=2009|pages totales=758|isbn=978-0-521-84425-3}}}}
* {{chapitre
| auteur1 = Jean-Michel Autebert
| auteur2 = Jean Berstel
| auteur3 = Luc Boasson
| titre chapitre = Context-free languages and pushdown automata
| auteurs ouvrage = G. Rozenberg et A. Salomaa (éditeurs)
| titre ouvrage = Handbook of Formal Languages
| éditeur = Springer Verlag
| année = 1997
| volume = 1
| titre volume = Word, Language, Grammar
| passage = 111--174
| isbn = 978-3540604204
}}
{{Palette|Informatique théorique}}
{{Portail|Informatique théorique}}

[[Catégorie:Théorie des automates]]
[[Catégorie:Calculabilité]]
[[Catégorie:Méthode formelle]]