System przejściowy

W informatyce teoretycznej system przejściowy jest koncepcją stosowaną w badaniu obliczeń . Służy do opisu potencjalnego zachowania systemów dyskretnych . Składa się ze stanów i przejść między stanami, które można oznaczyć etykietami wybranymi ze zbioru; ta sama etykieta może pojawić się na więcej niż jednym przejściu. Jeśli zestaw etykiet jest singletonem , system jest zasadniczo nieoznaczony i możliwa jest prostsza definicja, która pomija etykiety.

Systemy przejść pokrywają się matematycznie z abstrakcyjnymi systemami przepisywania (jak wyjaśniono dalej w tym artykule) i grafami skierowanymi . Różnią się one od automatów skończonych na kilka sposobów:

Zbiór stanów niekoniecznie jest skończony, a nawet policzalny.
Zbiór przejść niekoniecznie jest skończony, a nawet policzalny.
Nie podano stanu „początkowego” ani stanów „końcowych”.

Systemy przejść można przedstawić jako grafy skierowane.

Definicja formalna

Formalnie $rightarrow)}$ przejść to para, gdzie jest zbiorem stanów i jest relacją przejść stanów $( S , → )$ $,$ tj. podzbiór ${\ Displaystyle S \ razy S}$ ). Przejście ze stanu stanu tj. $displaystyle$ $p$ ${\ Displaystyle (p, q) \ w \ rightarrow }$ ) jest zapisywane jako ${\ Displaystyle p \ rightarrow q}$ .

Oznaczony system przejść $\ Displaystyle \ Lambda} to zbiór ( S ,$ krotka , gdzie jest zbiorem stanów, ${$ , $, \ Lambda, \ rightarrow)}$ etykiet, a $przejść$ (tj. podzbiorem ${\ displaystyle S \ razy \ Lambda \ razy S}$ ). ${\ Displaystyle (p, \ alfa, q) \ w \rightarrow}$ jest zapisane jako

{\ displaystyle p {\ overset {\ alfa} {\ rightarrow}} q \,}

i reprezentuje przejście ze stanu do stanu z etykietą . $}$ $p$ $displaystyle$ . Etykiety mogą przedstawiać różne rzeczy w zależności od języka, który Cię interesuje. Typowe zastosowania etykiet obejmują reprezentowanie oczekiwanych danych wejściowych, warunków, które muszą być spełnione, aby wyzwolić przejście, lub czynności wykonywanych podczas przejścia. Systemy oznaczonych przejść zostały pierwotnie wprowadzone jako nazwane systemy przejść.

Przypadki specjalne

Jeśli dla dowolnego danego $w$ istnieje $(p, \ alfa, q)}$ jedna krotka $Displaystyle$ → $\ displaystyle \rightarrow }$ , wtedy mówi się, $że$ jest ( $)$ .
$(p, \ alfa, q)}$ dowolnego danego $w$ istnieje co najmniej jedna krotka $Displaystyle$ → $\ displaystyle \rightarrow }$ , wtedy mówi się, $że$ jest ( $)$ .

Formalizacja teorii kategorii

Formalną definicję można przeformułować w kategoriach teorii kategorii. Każdy oznaczony system przejścia stanu $}$ $bijektywnie$ funkcją od $\ Displaystyle \ xi _ {\ rightarrow}$ { { S zestaw mocy indeksowany przez $\$ $displaystyle \ Lambda}$ zapisany jako ${\ Displaystyle {\ mathcal {P}} (\ Lambda \ razy S)}$ , zdefiniowane przez

{\ Displaystyle p \ mapsto \ {(\ alfa, q) \ w \ Lambda \ razy S: p {\ overset {\ alfa} {\ strzałka w prawo }}q\}}

.

$stanami$ system przejść między koalgebrą dla funktora

Relacja między oznakowanym i nieoznakowanym systemem przejściowym

Istnieje wiele relacji między tymi pojęciami. Niektóre są proste, jak na przykład obserwacja, że oznakowany system przejściowy, w którym zestaw etykiet składa się tylko z jednego elementu, jest równoważny nieoznaczonemu systemowi przejściowemu. Jednak nie wszystkie te relacje są równie trywialne.

Porównanie z abstrakcyjnymi systemami przepisywania

Jako obiekt matematyczny nieoznakowany system przejściowy jest identyczny z (nieindeksowanym) abstrakcyjnym systemem przepisywania . Jeśli potraktujemy relację przepisywania jako indeksowany zbiór relacji, jak robią to niektórzy autorzy, to system przejścia z etykietami jest równoważny abstrakcyjnemu systemowi przepisywania, w którym indeksy są etykietami. Przedmiot badań i terminologia są jednak różne. W systemie przejściowym interesuje nas interpretacja etykiet jako działań, podczas gdy w abstrakcyjnym systemie przepisywania nacisk kładziony jest na to, w jaki sposób obiekty mogą być przekształcane (przepisywane) w inne.

Rozszerzenia

Podczas sprawdzania modelu system przejściowy jest czasami definiowany tak, aby zawierał również dodatkową funkcję etykietowania dla stanów, co skutkuje pojęciem obejmującym strukturę Kripkego .

Języki akcji są rozszerzeniami systemów przejściowych, dodając zestaw fluentów F , zestaw wartości V i funkcję, która odwzorowuje F × S na V .

Zobacz też