System of transition from states

A system of transition from states , or automat in the broad sense, is a Modèle of abstract Machine, used in theoretical data processing to simulate the course of a calculation.

It consists of the data of a whole of states, and a whole of transitions from a state to another. In other words, the formal definition of a system of transition from states is a couple:

(S, \ rightarrow)

with

\ rightarrow \ in S \ times S

, where S is the whole of the states, and

\ rightarrow

is the relation of transition.

If p and Q is two states,

(p, Q) \ in \ rightarrow

wants to say that there exists a transition from p to Q , and also

p \ rightarrow q

is noted.

It should be noted that one makes no assumption a priori on S and $\ rightarrow$ , and that they can be infinite very well, even indénombrables. However, if S is finished (and thus $\ rightarrow$ also), the system of transition is a graph directed.

One can also give a definition labelled of system of transition: at this time, it is necessary moreover give oneself a whole of labels Λ, and to take $\ rightarrow \ in S \ times \ Lambda \ times S$ . The system of transition is then the triplet $(S, \ Lambda, \ rightarrow)$ . If there exists a transition labelled by $\ lambda \ in \ Lambda$ between two states p and Q , $then is noted
p \ stackrel {\ lambda} {\ rightarrow} q$ .

If S and Λ is finished, one will speak about automats of finished states (in general, one will give oneself also a condition of acceptance of word of entry, who will be often the data of two parts of S which will be the initial states, and the states acceptors).

The system of transitions is known as deterministic if and only if $\ rightarrow$ is a “function”, and not-determinist if not. Note that, in case labelled, this definition specifies not if one wants function of S in $\ Lambda \ times S$ , or of $S \ times \ Lambda$ in S (what one wants within the framework of the automats of finished states), or of $S \ times \ Lambda_1$ in $\ Lambda_2 \ times S$ if $\ Lambda= \ Lambda_1 \ times \ Lambda_2$ (case of the transducers).

The systems of transitions play a big role in the recognition of the formal languages, in particular in their classification.

current Examples:

Machine of Turing
Automat of finished states
Petri net
Graph directed
System of transitions associated with an operational Semantic

Random links: