Système de transition d'états

Un article de Wikipédia, l'encyclopédie libre.

Un système de transition d'états, ou automate au sens large, est un modèle de machine abstraite, 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. Autrement dit, la définition formelle d'un système de transition d'états est un couple :

$(S,\rightarrow)$ avec $\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\rightarrow$ veut dire qu'il existe une transition de p à q, et se note aussi $p\rightarrow q$ .

Il faut noter qu'on ne fait aucune hypothèse a priori sur S et $\rightarrow$ , et qu'ils peuvent très bien ê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 $\rightarrow\subset S\times\Lambda\times S$ . Le système de transition est alors le triplet $(S,\Lambda,\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$ .

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).

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).