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

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. +more 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

p \overset{\alpha}{\rightarrow} q \,

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

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.

Kategorie:Výpočetní modely