Diagram stanów - State diagram

Diagram stanu dla drzwi, które można tylko otwierać i zamykać

Diagram stanów to rodzaj schematu stosowanego w informatyce i dziedzin pokrewnych do opisania zachowania systemów. Diagramy stanów wymagają, aby opisany system składał się ze skończonej liczby stanów ; czasami tak jest w istocie, podczas gdy innym razem jest to rozsądna abstrakcja . Istnieje wiele form diagramów stanu, które różnią się nieznacznie i mają różną semantykę .

Przegląd

Diagram stanów są używane dać abstrakcyjny opis zachowań z systemu . To zachowanie jest analizowane i reprezentowane przez serię zdarzeń, które mogą wystąpić w co najmniej jednym możliwym stanie. W ten sposób „każdy diagram zazwyczaj przedstawia obiekty jednej klasy i śledzi różne stany swoich obiektów w systemie”.

Diagramy stanów mogą służyć do graficznego przedstawiania maszyn o skończonych stanach (zwanych również automatami skończonymi). Zostało to wprowadzone przez Claude'a Shannona i Warrena Weavera w ich książce z 1949 roku The Mathematical Theory of Communication . Innym źródłem jest Taylor Booth w swojej książce Sequential Machines and Automata Theory z 1967 roku . Inną możliwą reprezentacją jest tabela przejść stanów .

Kierowany wykres

Skierowane wykres

Klasyczną formą diagramu stanu automatu skończonego (FA) jest graf skierowany z następującymi elementami (Q, Σ, Z, δ, q 0 , F):

  • Wierzchołki Q : skończony zbiór stanów, zwykle reprezentowanych przez okręgi i oznaczonych unikalnymi symbolami desygnatora lub słowami zapisanymi w nich
  • Symbole wejściowe Σ : skończony zbiór symboli wejściowych lub desygnatorów
  • Symbole wyjściowe Z : skończony zbiór symboli wyjściowych lub desygnatorów

Funkcja wyświetlania ω oznacza mapowanie uporządkowanych par symboli wejściowych i stanów na symboli wyjściowych oznaczone matematycznie jako Ohm  : Σ x P → Z .

  • Krawędzie δ : reprezentują przejścia z jednego stanu do drugiego spowodowane wejściem (identyfikowane przez ich symbole narysowane na krawędziach). Krawędź jest zwykle rysowana jako strzałka skierowana z obecnego stanu do następnego stanu. To odwzorowanie opisuje przejście stanu, które ma nastąpić na wejściu określonego symbolu. Jest to zapisane matematycznie jako δ  : Q × Σ → Q , więc δ (funkcja przejścia) w definicji FA jest dana zarówno przez parę wierzchołków połączonych krawędzią, jak i symbol na krawędzi na diagramie przedstawiającym tę FA . Pozycja δ (q, a) = p w definicji FA oznacza, że ​​od stanu o nazwie q pod symbolem wejściowym a , w tej maszynie następuje przejście do stanu p . W wykres przedstawiający to FA, jest to reprezentowane przez krawędź znakowany w skierowaną od wierzchołka znakowany P do wierzchołka znakowany P .
  • Stan początkowy q 0 : (nie pokazany w poniższych przykładach). Stan początkowy q 0 ∈ Q jest zwykle reprezentowany przez strzałkę bez początku wskazującego stan. W starszych tekstach stan początkowy nie jest wyświetlany i należy go wywnioskować z tekstu.
  • Akceptowanie stanów F : Jeśli używane, na przykład do akceptowania automatów, F ∈ Q jest akceptującym stanem . Zwykle jest rysowany jako podwójne kółko. Czasami stany akceptacji funkcjonują jako stany „ F inal” (zatrzymane, uwięzione).

W przypadku deterministycznego automatu skończonego (DFA), niedeterministycznego automatu skończonego (NFA), uogólnionego niedeterministycznego automatu skończonego (GNFA) lub maszyny Moore'a , dane wejściowe są oznaczane na każdej krawędzi. W przypadku maszyny Mealy wejście i wyjście są oznaczone na każdej krawędzi, oddzielone ukośnikiem „/”: „1/0” oznacza zmianę stanu po napotkaniu symbolu „1”, powodując wyprowadzenie symbolu „0”. W przypadku maszyny Moore'a wyjście stanu jest zwykle zapisywane wewnątrz koła stanu, również oddzielone od oznaczenia stanu ukośnikiem „/”. Istnieją również warianty, które łączą te dwie notacje.

Na przykład, jeśli stan ma kilka wyjść (np. „A = silnik przeciwnie do ruchu wskazówek zegara = 1, b = światło ostrzegawcze nieaktywne = 0”) schemat powinien to odzwierciedlać: np. „Q5 / 1,0” oznacza stan q5 z wyjścia a = 1, b = 0. Ten desygnator zostanie zapisany wewnątrz koła stanu.

Przykład: maszyna DFA, NFA, GNFA lub Moore

S 1 i S 2 są stanami, a S 1 jest stanem akceptującym lub stanem końcowym . Każda krawędź jest oznaczona wejściem. Ten przykład pokazuje akceptor dla liczb binarnych zawierających parzystą liczbę zer.

DFAexample.svg

Przykład: maszyna Mealy

S 0 , S 1 i S 2 to stany. Każda krawędź jest oznaczona jako „ j / k ”, gdzie j to wejście, a k to wyjście.

Diagram stanu prostej maszyny Mealy

Harel statechart

Diagram przedstawiający wpływ wykresów stanu Harela na metody obiektowe i notację

Karty statystyk Harela, wynalezione przez informatyka Davida Harela , zyskują powszechne zastosowanie, odkąd wariant stał się częścią Unified Modeling Language (UML). Typ diagramu umożliwia modelowanie superpaństw , regionów ortogonalnych i działań jako części państwa.

Klasyczne diagramy stanu wymagają utworzenia odrębnych węzłów dla każdej poprawnej kombinacji parametrów definiujących stan. Może to prowadzić do bardzo dużej liczby węzłów i przejść między węzłami dla wszystkich systemów oprócz najprostszych ( eksplozja stanu i przejścia ). Ta złożoność zmniejsza czytelność diagramu stanu. Dzięki wykresom stanu Harela możliwe jest modelowanie wielu diagramów stanu o różnych funkcjach w ramach schematu stanu. Każdy z tych wielofunkcyjnych automatów stanów może przejść wewnętrznie bez wpływu na inne automaty stanu w schemacie stanów. Bieżący stan każdej wielofunkcyjnej maszyny stanu w schemacie stanów definiuje stan systemu. Wykres stanu Harela jest odpowiednikiem diagramu stanu, ale poprawia czytelność diagramu wynikowego.

Alternatywna semantyka

Istnieją inne zestawy semantyki do reprezentowania diagramów stanów. Na przykład istnieją narzędzia do modelowania i projektowania logiki dla kontrolerów wbudowanych. Diagramy te, podobnie jak oryginalne maszyny stanu Harela, obsługują hierarchicznie zagnieżdżone stany, regiony ortogonalne, akcje stanów i akcje przejścia.

Diagramy stanu a schematy blokowe

Nowicjusze w formalizmie automatu stanowego często mylą diagramy stanów ze schematami blokowymi . Poniższy rysunek przedstawia porównanie diagramu stanu ze schematem blokowym. Automat stanowy (panel (a)) wykonuje akcje w odpowiedzi na wyraźne zdarzenia. W przeciwieństwie do tego schemat blokowy (panel (b)) nie wymaga wyraźnych zdarzeń, ale raczej przejścia od węzła do węzła na swoim wykresie automatycznie po zakończeniu działań.

Diagram stanu (a) i schemat blokowy (b)

Węzły schematów blokowych są krawędziami indukowanego wykresu stanów. Powodem jest to, że każdy węzeł w schemacie blokowym reprezentuje polecenie programu. Polecenie programu to czynność do wykonania. Nie jest to więc stan, ale zastosowany do stanu programu powoduje przejście do innego stanu.

Bardziej szczegółowo, lista kodu źródłowego przedstawia wykres programu. Wykonanie wykresu programu (parsowanie i interpretacja) skutkuje powstaniem wykresu stanu. Zatem każdy wykres programu wywołuje wykres stanu. Konwersja wykresu programu do skojarzonego z nim wykresu stanu nazywana jest „rozwijaniem” wykresu programu.

Wykres programu to sekwencja poleceń. Jeśli nie istnieją żadne zmienne, to stan składa się tylko z licznika programu, który śledzi, gdzie w programie się znajdujemy podczas wykonywania (jakie jest następne polecenie do wykonania).

W tym przypadku przed wykonaniem polecenia licznik programu znajduje się na jakiejś pozycji (stan przed wykonaniem polecenia). Wykonanie polecenia przenosi licznik programu do następnego polecenia. Ponieważ licznikiem programu jest cały stan, wynika z tego, że wykonanie polecenia zmieniło stan. Zatem samo polecenie odpowiada przejściu między dwoma stanami.

Rozważmy teraz cały przypadek, kiedy istnieją zmienne i mają na nie wpływ wykonywane polecenia programu. Wtedy między różnymi lokalizacjami liczników programu nie tylko zmienia się licznik programu, ale zmienne mogą również zmieniać wartości w wyniku wykonywanych poleceń. W konsekwencji, nawet jeśli ponownie odwiedzimy jakieś polecenie programu (np. W pętli), nie oznacza to, że program jest w tym samym stanie.

W poprzednim przypadku program byłby w tym samym stanie, ponieważ cały stan jest tylko licznikiem programu, więc jeśli program kontrapunktuje na tę samą pozycję (następne polecenie), wystarczy określić, że jesteśmy w tym samym stanie. Jeśli jednak stan zawiera zmienne, to jeśli zmieniają one wartość, możemy znajdować się w tym samym miejscu programu z różnymi wartościami zmiennych, czyli w innym stanie w przestrzeni stanów programu. Termin „rozwijanie” wywodzi się z tego mnożenia lokalizacji podczas tworzenia wykresu stanu na podstawie wykresu programu.

Przejście samoistne to przejście, w którym stan początkowy i końcowy są takie same.

Reprezentatywnym przykładem jest pętla do, która zwiększa wartość licznika, aż przepełni się i ponownie osiągnie wartość 0. Chociaż pętla do wykonuje iteracyjnie to samo polecenie inkrementacji, więc wykres programu wykonuje cykl, w swojej przestrzeni stanów nie jest cyklem, ale linią. Wynika to ze stanu będącego lokalizacją programu (tutaj cyklicznie) połączonego z wartością licznika, która ściśle rośnie (do przepełnienia), a więc kolejno odwiedzane są różne stany, aż do przepełnienia. Po przepełnieniu licznik ponownie staje się 0, więc stan początkowy jest ponownie odwiedzany w przestrzeni stanów, zamykając cykl w przestrzeni stanów (zakładając, że licznik został zainicjowany na 0).

Powyższy rysunek próbuje pokazać to odwrócenie ról poprzez dopasowanie łuków diagramów stanu do etapów przetwarzania schematu blokowego.

Możesz porównać schemat blokowy z linią montażową w produkcji, ponieważ schemat blokowy opisuje postęp jakiegoś zadania od początku do końca (np. Przekształcanie wejścia kodu źródłowego na kod wynikowy przez kompilator). Automat stanowy generalnie nie ma pojęcia o takiej progresji. Maszyna stanu drzwi pokazana na początku tego artykułu, na przykład, nie jest w bardziej zaawansowanym stadium, gdy jest w stanie „zamkniętym” w porównaniu do stanu „otwartego”; po prostu inaczej reaguje na zdarzenia otwarcia / zamknięcia. Stan w automacie stanów jest skutecznym sposobem określania określonego zachowania, a nie etapem przetwarzania.

Inne rozszerzenia

Ciekawym rozszerzeniem jest umożliwienie przepływu łuków z dowolnej liczby stanów do dowolnej liczby stanów. Ma to sens tylko wtedy, gdy system może znajdować się w wielu stanach jednocześnie, co oznacza, że ​​pojedynczy stan opisuje tylko stan lub inny częściowy aspekt ogólnego stanu globalnego. Powstały formalizm jest znany jako sieć Petriego .

Kolejne rozszerzenie umożliwia integrację schematów blokowych w statecharts Harel. To rozszerzenie obsługuje tworzenie oprogramowania, które jest sterowane zarówno zdarzeniami, jak i przepływem pracy.

Zobacz też

Bibliografia

Linki zewnętrzne