title: Sistema a transizione di stati
text: # 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.
  
  