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.