Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Système de transition d'états
Résumé
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.
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.
Un système de transition d'états étiqueté 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).
Dans le cas où et sont finis, on parle d'automate fini (ou machine à états finie).
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.
Les systèmes de transitions jouent un rôle important dans la reconnaissance des langages formels, notamment dans leur classification.
En vérification de modèles (), les systèmes de transitions d'états possèdent en plus une fonction d'étiquetage pour les états (voir par exemple structure de Kripke).
Un système d'états-transitions non étiqueté est un .
Automate d'états finis
Réseau de Petri
Graphe orienté
M
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.