Sistema a transizione di stati

In informatica teorica un sistema a transizione di stati è una macchina astratta usata nella teoria della computazione. In letteratura viene indicato con LTS dal nome inglese Labelled Transition System. La macchina consiste di un insieme di stati e transizioni tra gli stati, che possono essere etichettate con etichette scelte da un insieme; la stessa etichetta può apparire su più di una transizione. Se l'insieme delle etichette è composto da un solo elemento, il sistema è essenzialmente privo di etichette, e una definizione più semplice che omette le etichette è possibile.

I sistemi a transizione di stati differiscono comunque dagli automi a stati finiti in più modi:

• In un sistema a transizione di stati l'insieme di stati non è necessariamente finito o numerabile.
• In un sistema a transizione di stati l'insieme delle transizioni non è necessariamente finito o numerabile.

I sistemi a transizione di stati possono essere rappresentati come grafi orientati.

Definizione Formale

Formalmente, un Sistema a transizione di stati è una coppia (S, →) dove S è un insieme (di stati) e → ⊆ S×S è una relazione binaria su S (di transizioni). Se p, q ∈ S, (p, q) ∈ → è solitamente scritto come p → q. Questo rappresenta il fatto che esiste una transizione dallo stato p allo stato q.

Un sistema a transizioni etichettato è una tripla (S, Λ, →) dove S è un insieme (di stati), Λ è un insieme (di etichette) e → ⊆ S×Λ×S è una relazione ternaria (di transizioni etichettate). Se p, q ∈ S e α ∈ Λ, allora (p,α,q) ∈ → è scritto come.

$p{\overset {\alpha }{\rightarrow }}q.\,$

Questo rappresenta il fatto che c'è una transizione dallo stato p allo stato q con etichetta α. Una etichetta può rappresentare cose differenti a seconda del linguaggio di interesse. Usi tipici delle etichette includono il rappresentare un input atteso, condizioni che devono essere vere per attivare la transizione, o azioni effettuate durante la transizione.

Voci correlate

• Bisimulazione
• Simulazione (informatica)

Controllo di autorità	GND (DE) 4329099-1