Přechodový systém
Přechodový systém je v teoretické informatice abstraktní stroj používaný pro studium výpočtů a chování procesů. Stroj sestává z množiny stavů a z přechodů mezi stavy.
Přechodové systémy se dělí na „označené“ (labelled) a „neoznačené“ (unlabelled).
Definice
[editovat | editovat zdroj]Neoznačený přechodový systém je uspořádaná dvojice (S, →), kde S je množina stavů a → ⊆ S × S je binární relace nad touto množinou, která popisuje možné přechody. Pokud platí, že p,q ∈ S a (p,q) ∈ → pak obvykle píšeme p → q. Znamená to, že existuje přechod ze stavu p do stavu q.
Označený přechodový systém je trojice (S, Λ, →), kde S je množina stavů, Λ je množina označení a → ⊆ S × Λ × S je ternární relace. Pokud p, q ∈ S a α ∈ Λ, (p,α,q) ∈ →, píšeme
Znamená to, že v systému existuje přechod ze stavu p do stavu q, který je označený prvkem α. Tyto „značky“ mohou představovat různé věci – například očekávaný vstup do systému, podmínky, které musí platit nebo akce, které se provedou během přechodu.
Vlastnosti
[editovat | editovat zdroj]Přechodový systém je podobný konečnému automatu, liší se však v následujících vlastnostech:
- množina stavů přechodového systému nemusí být konečná ani spočetná.
- množina přechodů přechodového systému nemusí být konečná ani spočetná.
Přechodové systémy s konečným počtem stavů a přechodů lze reprezentovat jako orientované grafy.
