Epsilon transitionEn informatique théorique, et notamment en théorie des automates, une epsilon transition, notée aussi ε-transition et appelée également transition spontanée[1] 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 importantsDes cas particuliers importants sont notamment : Élimination des ε-transitions dans un automate finiL'automate ci-contre est asynchrone : il possède une ε-transition de l'état 1 vers l'état 2. L'élimination des -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[2], comme suit :
Pour les états initiaux et terminaux, on complète par :
Bien entendu, on supprime les -transitions. Dans l'exemple de la figure, on ajoute la transition dans la première étape en fermeture arrière, et on déclare que est état final dans la deuxième étape. Si on opère par fermeture avant, on ajoute la transition et on déclare 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 à pileUne 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[3] 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 TuringLa 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
Bibliographie
|