Système de transition d'états

Cet article ne cite pas suffisamment ses sources (juillet 2012). 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 ». (Modifier l'article)

En informatique théorique, un système de transition d'états, ou automate au sens large, est un modèle de machine abstraite (en), utilisé en informatique théorique pour simuler le déroulement d'un calcul.

Il consiste en la donnée d'un ensemble d'états, et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées à partir d'un ensemble d'étiquettes, une même étiquette pouvant apparaître sur plusieurs transitions. Si cet ensemble est un singleton, on peut omettre l'étiquetage.

Les systèmes d'états transitions coïncident mathématiquement avec les systèmes abstraits de réécriture (en) (voir plus loin). Ils diffèrent néanmoins des systèmes de réécritures :

• l'ensemble des états peut être infini ou même indénombrable;
• l'ensemble des transitions peut être infini ou même indénombrable;
• Un automate à états fini possède un état initial et un ensemble d'états finaux.

Les systèmes d'états-transitions peuvent être représentés comme des graphes orientés

Définitions formelles

Un système de transition d'états (non étiqueté) est

Un couple $(S,\mathord\rightarrow)$ avec $\mathord\rightarrow\subset S\times S$, où S est l'ensemble des états, et $\rightarrow$ est la relation de transition.

Si p et q sont deux états, $(p,q)\in\mathord{\rightarrow}$ veut dire qu'il existe une transition de p à q, et se note aussi $p\rightarrow q$.

On ne fait aucune hypothèse a priori sur S et $\rightarrow$, et ils peuvent être infinis, voire indénombrables. Cependant, si S est fini (et donc $\rightarrow$ aussi), le système de transition est un graphe orienté.

On peut aussi donner une définition étiquetée de système de transition : à ce moment, il faut de plus se donner un ensemble d'étiquettes Λ, et prendre $\mathord\rightarrow\subset S\times\Lambda\times S$. Le système de transition est alors le triplet $(S,\Lambda,\mathord\rightarrow)$. S'il existe une transition étiquetée par $\lambda \in\Lambda$ entre deux états p et q, on note alors $p \stackrel{\lambda}{\rightarrow} q$.

Machine à états fini

Dans le cas où S et Λ sont finis, on parlera d'automates d'états finis (en général, on se donnera aussi une condition d'acceptation de mot d'entrée, qui sera souvent la donnée de deux parties de S qui seront les états initiaux, et les états accepteurs).

Système déterministe

Le système de transitions est dit déterministe si et seulement si $\rightarrow$ est une « fonction », et non-déterministe sinon.

Dans le cas étiqueté, cette définition ne précise pas si on veut une fonction de S dans $\Lambda\times S$, ou de $S\times\Lambda$ dans S (ce qu'on veut dans le cadre des automates d'états finis), ou encore de $S\times\Lambda_1$ dans $\Lambda_2\times S$ si $\Lambda=\Lambda_1\times\Lambda_2$ (cas des transducteurs).

Applications et variantes

Applications courantes

Les systèmes de transitions jouent un rôle important dans la reconnaissance des langages formels, notamment dans leur classification.

En model checking, les systèmes d'états transitions sont définis munis une fonction additionnelle d'étiquetage pour des états, le résultat englobant alors une structure de Kripke

Exemples courants de systèmes d'états transition

• Machine de Turing
• Automate d'états finis
• Réseau de Petri
• Graphe orienté
• Système de transitions associé à une sémantique opérationnelle

Comparaison avec les systèmes abstraits de réécriture (SAB)

En tant qu'objet mathématique, un système d'états transition (SET) non étiqueté est identique à un SAB non indexé. Si nous considérons la relation de réécriture comme un ensemble indexé de relations, comme on le fait parfois, alors un SET étiqueté et un SAB indexé par les étiquettes sont structurellement équivalents. Les différences de domaine tiennent à sur quoi est mis l'accent de l'étude et à la terminologie. Dans un SET on s'intéresse à interpréter les étiquettes comme des actions, tandis qu'à travers un ABS on s'intéresse plutôt à la manière dont un objet est transformé (réécrit) en un autre.

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)