Sistem de tranziție de stat
În informatică teoretică, un sistem de stare de tranziție este o mașină abstractă utilizată în teoria calculelor . În literatură este indicat cu LTS din denumirea în engleză Labeled Transition System. Mașina constă dintr-un set de stări și tranziții între stări, care pot fi etichetate cu etichete alese dintr-un set; aceeași etichetă poate apărea în mai multe tranziții. Dacă setul de etichete este format dintr-un singur element , sistemul este în esență lipsit de etichete și este posibilă o definiție mai simplă care omite etichetele.
Cu toate acestea, sistemele de tranziție de stare diferă de automatele de stare finită în mai multe moduri:
- Într-un sistem de tranziție de stat, setul de stări nu este neapărat finit sau numărabil.
- Într-un sistem de tranziție de stare, setul de tranziții nu este neapărat finit sau numărabil.
Sistemele de tranziție de stat pot fi reprezentate ca grafice orientate.
Definiție formală
În mod formal, un sistem de tranziție de stare este o pereche ( S , →) unde S este un set (de stări) și → ⊆ S × S este o relație binară pe S (de tranziții). Dacă p , q ∈ S , ( p , q ) ∈ → se scrie de obicei ca p → q . Aceasta reprezintă faptul că există o tranziție de la starea p la starea q .
Un sistem de tranziție etichetat este un triplu ( S , Λ, →) unde S este un set (de stări), Λ este un set (de etichete) și → ⊆ S × Λ × S este o relație ternară (a tranzițiilor etichetate). Dacă p , q ∈ S și α ∈ Λ, atunci ( p , α, q ) ∈ → se scrie ca.
Aceasta reprezintă faptul că există o tranziție de la starea p la starea q cu eticheta α. O etichetă poate reprezenta diferite lucruri în funcție de limba de interes. Utilizările tipice ale etichetelor includ reprezentarea unei intrări așteptate, condiții care trebuie să fie adevărate pentru a declanșa tranziția sau acțiuni întreprinse în timpul tranziției.
Elemente conexe
| Controlul autorității | GND ( DE ) 4329099-1 |
|---|
