Přechodový systém

Z Wikipedie, otevřené encyklopedie

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,qS a (p,q) ∈ → pak obvykle píšeme pq. 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, qS 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.