Système de transition d'états

Système de transition d'états

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.

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

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

Exemples courants 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Système de transition d'états de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Systeme de transition d'etats — Système de transition d états 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… …   Wikipédia en Français

  • Transition structurelle — Transition Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Transition — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Transition », sur le Wiktionnaire (dictionnaire universel) en mathématiques : une matrice de… …   Wikipédia en Français

  • transition — [ trɑ̃zisjɔ̃ ] n. f. • 1501 « procédé rhétorique »; lat. transitio, proprt « passage » 1 ♦ Manière de passer de l expression d une idée à une autre, de lier les parties d un discours. ⇒ passage. L art des transitions. Ménager les transitions.… …   Encyclopédie Universelle

  • SYSTÈME (épistémologie) — La notion de système apparaît dans deux catégories de contextes, fort différentes: d’une part, lorsqu’il est question de propositions (dans lesquelles sont exprimées des relations formelles ou des conceptions relatives à la réalité), d’autre part …   Encyclopédie Universelle

  • Transition d'IPv4 vers IPv6 — Pour consulter un article plus général, voir : IPv6. La transition d IPv4 vers IPv6 est un processus qui vise au remplacement progressif du protocole IPv4 par IPv6 sur Internet. Sommaire 1 Phases de la transition 2 Transition pour des hôtes… …   Wikipédia en Français

  • Système international (relations internationales) — Pour les articles homonymes, voir Système international (homonymie). La notion de système international est utilisé en théorie des relations internationales, en géopolitique et en droit international afin de désigner, principalement, les… …   Wikipédia en Français

  • ÉTATS-UNIS - La littérature américaine — Le goût qu’ont les lecteurs européens pour la littérature des États Unis n’est pas une mode passagère. On a pu croire que les troupes de la Libération avaient apporté Hemingway dans leurs bagages et que l’âge du roman américain ne durerait pas.… …   Encyclopédie Universelle

  • Transition demographique — Transition démographique La théorie de la transition démographique part d un constat simple à savoir que les variations spatiales de la mortalité et de la natalité sont dues à des différences d évolution démographique. Le schéma de la transition… …   Wikipédia en Français

  • ÉTATS-UNIS - Histoire — L’histoire des États Unis est celle de l’ascension extrêmement rapide de colonies sous domination anglaise au stade de grande puissance mondiale. Les premiers colons débarquent en Virginie au XVIIe siècle, leurs descendants obtiennent leur… …   Encyclopédie Universelle

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”