| dbpprop:abstract
|
- In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible. State transition systems coincide mathematically with abstract rewriting systems (as explained further in this article). State transition systems differ however from finite state automata in several ways: In a state transition system the set of states is not necessarily finite, or even countable. In a state transition system the set of transitions is not necessarily finite, or even countable. State transition systems can be represented as directed graphs.
- Ein Transitionssystem (engl. transition system) beschreibt in der Automatentheorie die möglichen Zustände eines zustandsbasierten Systems und die möglichen Übergänge (Transitionen) zwischen diesen Zuständen. Man unterscheidet dabei diskrete und kontinuierliche Systeme. In der Regel betrachtet man nur diskrete Systeme, da diese wesentlich leichter überprüft werden können. Ferner unterscheidet man deterministische und nichtdeterministische Transitionssysteme. Im ersten Fall wird einem Zustand und einer Transition höchstens ein Folgezustand zugeordnet, während im nichtdeterministischen Fall derselbe Zustand zu einer Transition mehrere Nachfolgezustände besitzen kann. Deterministische Transitionssysteme sind in diesem Sinne Spezialfälle von nichtdeterministischen Transitionssystemen. Ein Transitionssystem kann verwendet werden, um bestimmte Eigenschaften eines zustandsbasierten Systems zu zeigen, insbesondere die Terminiertheit. Aus diesem Grund wird es zur Verifikation der Korrektheit von Algorithmen eingesetzt. Auch zum Beweis der Verklemmungsfreiheit von verteilten Systemen kann dieses Konstrukt angewendet werden.
- Přechodový systém je v teoretické informatice abstraktní stroj používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy. Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled).
- 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 : <math>(S,\rightarrow)</math> avec <math>\rightarrow\subset S\times S</math>, où S est l'ensemble des états, et <math>\rightarrow</math> est la relation de transition. Si p et q sont deux états, <math>(p,q)\in\rightarrow</math> veut dire qu'il existe une transition de p à q, et se note aussi <math>p\rightarrow q</math>. On ne fait aucune hypothèse a priori sur S et <math>\rightarrow</math>, et ils peuvent être infinis, voire indénombrables. Cependant, si S est fini (et donc <math>\rightarrow</math> 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 <math>\rightarrow\subset S\times\Lambda\times S</math>. Le système de transition est alors le triplet <math>(S,\Lambda,\rightarrow)</math>. S'il existe une transition étiquetée par <math>\lambda \in\Lambda</math> entre deux états p et q, on note alors <math> p \stackrel{\lambda}{\rightarrow} q</math>. 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 <math>\rightarrow</math> 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 <math>\Lambda\times S</math>, ou de <math>S\times\Lambda</math> dans S (ce qu'on veut dans le cadre des automates d'états finis), ou encore de <math>S\times\Lambda_1</math> dans <math>\Lambda_2\times S</math> si <math>\Lambda=\Lambda_1\times\Lambda_2</math>. Les systèmes de transitions jouent un rôle important dans la reconnaissance des langages formels, notamment dans leur classification. Exemples courants Machine de Turing Automate d'états finis Réseau de Petri Graphe orienté Système de transitions associé à une sémantique opérationnelle
- 状態遷移系（じょうたいせんいけい、State Transition System）とは、理論計算機科学での計算の研究に使用される抽象機械の一種。状態遷移系は状態群と状態間の遷移から構成される。 状態遷移系と有限オートマトンは以下のような点で異なる: 状態遷移系では状態数は有限である必要はなく、枚挙可能である必要もない。 状態遷移系では遷移数は有限である必要はなく、枚挙可能である必要もない。 状態と遷移が有限個の状態遷移系は有向グラフで表すことができる。 また、状態遷移系は「ラベル付き」と「ラベル無し」の2種類に分類することができる。
- Модель станів і переходів — абстрактний автомат, використовується для дослідження обчислень. Модель складається із множини станів та переходів між станами. Моделі станів та переходів мають декілька відмінностей від скінченних автоматів: Моделі станів і переходів мають не обов'язково скінченну або зліченну кількість станів Моделі станів і переходів мають не обов'язково скінченну або зліченну множину переходів Моделі станів і переходів із скінченною кількістю станів та переходів можна представити у вигляді орієнтованих графів. Існує щонайменше два типи моделей станів і переходів: марковані та немарковані.
|
| rdfs:comment
|
- In theoretical computer science, a state transition system is an abstract machine used in the study of computation. The machine consists of a set of states and transitions between states, which may be labeled with labels chosen from a set; the same label may appear on more than one transition. If the label set is a singleton, the system is essentially unlabeled, and a simpler definition that omits the labels is possible.
- Ein Transitionssystem (engl. transition system) beschreibt in der Automatentheorie die möglichen Zustände eines zustandsbasierten Systems und die möglichen Übergänge (Transitionen) zwischen diesen Zuständen. Man unterscheidet dabei diskrete und kontinuierliche Systeme. In der Regel betrachtet man nur diskrete Systeme, da diese wesentlich leichter überprüft werden können. Ferner unterscheidet man deterministische und nichtdeterministische Transitionssysteme.
- Přechodový systém je v teoretické informatice abstraktní stroj používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy. Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled).
- 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.
- Модель станів і переходів — абстрактний автомат, використовується для дослідження обчислень. Модель складається із множини станів та переходів між станами.
|
![[RDF Data]](/statics/sw-cube.png)
