Système de transition d'états
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
En informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s).
Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage.
Les systèmes d'états-transitions sont des graphes orientés.
Définitions formelles
Système de transition d'états non étiqueté
Un système de transition d'états non étiqueté est un couple , où est l'ensemble des états et est la relation de transition. Si et sont deux états, signifie qu'il existe une transition de à , et on l'écrit .
On ne fait aucune hypothèse a priori sur et , et ils peuvent être infinis, voire indénombrables.
Système étiqueté de transition d'états
Un système étiqueté de transition d'états est un triplet , avec l'ensemble des états, un ensemble d'étiquettes et la relation de transition. S'il existe une transition étiquetée par entre deux états et , on écrit alors .
Il est à noter que la définition de la relation de transition ne précise pas s'il s'agit d'une relation binaire :
- de dans (cas non pertinent dans le cadre des systèmes de transition d'états) ;
- de dans (cas des automates finis) ;
- de dans avec (cas des transducteurs finis).
Automate fini
Lorsque les ensembles et sont finis et si l'on se donne un ensemble d'états initiaux et un ensemble d'état acceptants (ou terminaux) , on parle d'automate fini (ou machine à états finie).
Système déterministe
Le système de transition est dit déterministe si par définition est une fonction. L'expression système de transition non déterministe qualifie tous les systèmes de transition d'états quand on a besoin de préciser qu'on ne se retreint pas aux systèmes déterministes.
Applications et variantes
Applications courantes
Les systèmes de transitions jouent un rôle important[Lequel ?] dans la reconnaissance des langages formels, notamment dans leur classification.
En vérification de modèles (en anglais : model checking), les systèmes de transitions d'états possèdent en plus une fonction d'étiquetage pour les états (voir par exemple structure de Kripke[1]).
Comparaison avec les systèmes abstraits de réécriture
Un système d'états-transitions non étiqueté est un système abstrait de réécriture (en)[2].
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « State transition system » (voir la liste des auteurs).
Voir aussi
- Automate d'états finis
- Réseau de Petri
- Graphe orienté
- Machines abstraites comme les machines de Turing, la machine de Krivine ou la machine SECD
- Système de transition associé à une sémantique opérationnelle
v · m Automates finis et langages réguliers | |
---|---|
Articles généraux | |
Automates finis | |
Automates finis particuliers |
|
Langages réguliers | |
Des automates aux langages | |
Des langages aux automates | |
Minimisation | |
Équivalences |
Portail de l’informatique
Portail de l'informatique théorique