Sistema a transizione di stati

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

In informatica teorica un sistema a transizione di stati è una macchina astratta usata nello studio della computazione. 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[modifica | modifica sorgente]

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, qS, (p, q) ∈ → è solitamente scritto come pq. 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, qS 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[modifica | modifica sorgente]