Stavový diagram - State diagram

Stavový diagram pro dveře, které lze otevřít a zavřít pouze

Stavový diagram je druh diagramu použitého v informatice a příbuzných oborech k popisu chování systémů. Stavové diagramy vyžadují, aby popsaný systém sestával z konečného počtu stavů ; někdy tomu tak skutečně je, jindy je to rozumná abstrakce . Existuje mnoho forem stavových diagramů, které se mírně liší a mají odlišnou sémantiku .

Přehled

Stavové diagramy se používají k vytváření abstraktní popis chování jednoho systému . Toto chování je analyzováno a reprezentováno řadou událostí, které mohou nastat v jednom nebo více možných stavech. Tímto způsobem „každý diagram obvykle představuje objekty jedné třídy a sleduje různé stavy svých objektů prostřednictvím systému“.

Stavové diagramy lze použít ke grafickému znázornění konečných stavových strojů (nazývaných také konečné automaty). Toto představili Claude Shannon a Warren Weaver ve své knize Matematická teorie komunikace z roku 1949 . Dalším zdrojem je Taylor Booth ve své knize Sekvenční stroje a teorie automatů z roku 1967 . Další možnou reprezentací je tabulka přechodu stavu .

Směrovaný graf

Klasickou formou stavového diagramu pro konečný automat (FA) je směrovaný graf s následujícími prvky (Q, Σ, Z, δ, q 0 , F):

  • Vrcholy Q : konečná sada stavů, obvykle reprezentovaná kruhy a označená jedinečnými označovacími symboly nebo slovy napsanými uvnitř nich
  • Vstupní symboly Σ : konečná kolekce vstupních symbolů nebo označení
  • Výstupní symboly Z : konečná kolekce výstupních symbolů nebo označení

Výstupní funkce ω představuje mapování uspořádaných dvojic vstupních symbolů a stavů na výstupních symbolů, označených matematicky jako W  : Σ x Q Z .

  • Hrany δ : představují přechody z jednoho stavu do druhého způsobené vstupem (identifikované podle jejich symbolů nakreslených na okrajích). Okraj je obvykle nakreslen jako šipka směřující z aktuálního stavu do dalšího stavu. Toto mapování popisuje přechod stavu, ke kterému má dojít na vstupu konkrétního symbolu. To se matematicky píše jako δ  : Q × Σ Q , takže δ (přechodová funkce) v definici FA je dána dvojicí vrcholů spojených hranou a symbolem na hraně v diagramu představujícím tuto FA . Položka δ (q, a) = p v definici FA znamená, že ze stavu pojmenovaného q pod vstupním symbolem a dochází v tomto stroji k přechodu do stavu p . V diagramu představující tuto FA, to je reprezentován hranou označeném a směřující od vrcholu označeném q k vrcholu označeném p .
  • Počáteční stav q 0 : (nezobrazeno v příkladech níže). Počáteční stav q 0 ∈ Q je obvykle reprezentován šipkou bez počátku ukazující na stav. Ve starších textech se počáteční stav nezobrazuje a musí být odvozen z textu.
  • Přijímající stav (y) F : Pokud se používá, například pro přijímání automatů, F ∈ Q je přijímající stav . Obvykle se kreslí jako dvojitý kruh. Někdy stavy přijetí fungují jako stavy „ F inal“ (halt, trapped).

Pro deterministický konečný automat (DFA), nedeterministický konečný automat (NFA), zobecněný nedeterministický konečný automat (GNFA) nebo Mooreův stroj je vstup označen na každé hraně. U stroje Mealy jsou vstup a výstup označeny na každé hraně a jsou odděleny lomítkem „/“: „1/0“ označuje změnu stavu při setkání se symbolem „1“, který způsobí, že bude výstupem symbol „0“. U stroje Moore je výstup stavu obvykle psán uvnitř kruhu státu, také oddělen od označení státu lomítkem „/“. Existují také varianty, které kombinují tyto dvě notace.

Například pokud má stav několik výstupů (např. „A = motor proti směru hodinových ručiček = 1, b = výstražné světlo neaktivní = 0“), mělo by to odrážet tento diagram: např. „Q5 / 1,0“ označuje stav q5 s výstupy a = 1, b = 0. Tento označení bude napsáno uvnitř kruhu státu.

Příklad: stroj DFA, NFA, GNFA nebo Moore

S 1 a S 2 jsou stavy a S 1 je přijetí stav nebo konečný stav . Každá hrana je označena vstupem. Tento příklad ukazuje akceptor pro binární čísla, která obsahují sudý počet nul.

DFAexample.svg

Příklad: Mealy stroj

S 0 , S 1 a S 2 jsou stavy. Každá hrana je označena „ j / k “, kde j je vstup a k je výstup.

Stavový diagram jednoduchého stroje Mealy

Harel Statechart

Diagram ukazující, jak Harel's Statecharts přispěly k objektově orientovaným metodám a notaci

Harelské státní mapy, které vynalezl počítačový vědec David Harel , získávají široké využití, protože varianta se stala součástí Unified Modeling Language (UML). Typ diagramu umožňuje modelovat superstáty , ortogonální oblasti a aktivity jako součást stavu.

Klasické stavové diagramy vyžadují vytvoření samostatných uzlů pro každou platnou kombinaci parametrů, které definují stav. To může vést k velkému počtu uzlů a přechodům mezi uzly pro všechny systémy kromě těch nejjednodušších ( exploze stavu a přechodu ). Tato složitost snižuje čitelnost stavového diagramu. S Harel statecharts je možné modelovat více cross-funkční stavové diagramy v rámci statechart. Každý z těchto křížově funkčních stavových automatů může interně přecházet bez ovlivnění ostatních stavových automatů ve stavovém diagramu. Aktuální stav každého křížově funkčního stavového stroje ve stavovém diagramu definuje stav systému. Harelův stavový diagram je ekvivalentní se stavovým diagramem, ale zlepšuje čitelnost výsledného diagramu.

Alternativní sémantika

K reprezentaci stavových diagramů jsou k dispozici další sady sémantiky. Například existují nástroje pro modelování a návrh logiky pro vložené řadiče. Tyto diagramy, stejně jako Hareliny původní stavové stroje, podporují hierarchicky vnořené stavy, ortogonální oblasti, akce stavu a akce přechodu.

Stavové diagramy versus vývojové diagramy

Nováčci formalismu státního stroje často zaměňují stavové diagramy s vývojovými diagramy . Na následujícím obrázku je srovnání stavového diagramu s vývojovým diagramem. Stavový automat (panel (a)) provádí akce v reakci na explicitní události. Naproti tomu vývojový diagram (panel (b)) nepotřebuje explicitní události, ale spíše přechody z uzlu do uzlu ve svém grafu automaticky po dokončení činností.

Stavový diagram (a) a vývojový diagram (b)

Uzly vývojových diagramů jsou hrany v indukovaném grafu stavů. Důvodem je, že každý uzel ve vývojovém diagramu představuje programový příkaz. Programový příkaz je akce, která se má provést. Nejedná se tedy o stav, ale při použití na stav programu vede k přechodu do jiného stavu.

Podrobněji výpis zdrojového kódu představuje programový graf. Provedení programového grafu (syntaktická analýza a interpretace) má za následek stavový graf. Každý programový graf tedy indukuje stavový graf. Převod programového grafu na související stavový graf se nazývá „rozvinutí“ programového grafu.

Graf programu je sledem příkazů. Pokud neexistují žádné proměnné, pak se stav skládá pouze z počitadla programu, který sleduje, kde se v programu během provádění nacházíme (jaký další příkaz bude použit).

V tomto případě je před provedením příkazu počítadlo programu v určité poloze (stav před provedením příkazu). Provedení příkazu přesune počítadlo programu na další příkaz. Vzhledem k tomu, že čítač programu je celý stav, vyplývá z toho, že provedení příkazu změnilo stav. Samotný příkaz tedy odpovídá přechodu mezi těmito dvěma stavy.

Nyní zvažte celý případ, kdy proměnné existují a jsou ovlivněny prováděnými příkazy programu. Pak se mezi různými umístěními počitadel programu nejen mění počitadlo programu, ale proměnné mohou také měnit hodnoty kvůli provedeným příkazům. Z toho vyplývá, že i když se vrátíme k nějakému příkazu programu (např. Ve smyčce), neznamená to, že je program ve stejném stavu.

V předchozím případě by byl program ve stejném stavu, protože celý stav je pouze počitadlo programu, takže pokud jsou kontrapunkty programu na stejné pozici (další příkaz), stačí určit, že jsme ve stejném stavu. Pokud však stav zahrnuje proměnné, pak pokud tyto změní hodnotu, můžeme být na stejném místě programu s různými hodnotami proměnných, což znamená v jiném stavu ve stavovém prostoru programu. Termín „rozvinutí“ pochází z tohoto násobení míst při vytváření stavového grafu z grafu programu.

Vlastní přechod je přechod, při kterém jsou počáteční a konečný stav stejné.

Reprezentativním příkladem je smyčka do, která zvyšuje nějaký čítač, dokud nepřeteče a nezmění se znovu na 0. Ačkoli smyčka do provádí iterativně stejný příkaz přírůstku, takže programový graf provede cyklus, v jeho stavovém prostoru není cyklus, ale čára. To vyplývá ze stavu, který je umístěním programu (zde cykluje) v kombinaci s hodnotou čítače, která se striktně zvyšuje (do přetečení), takže se postupně navštěvují různé stavy, až do přetečení. Po přetečení se počitadlo opět změní na 0, takže ve stavovém prostoru se znovu objeví počáteční stav, čímž se uzavře cyklus ve stavovém prostoru (za předpokladu, že počitadlo bylo inicializováno na 0).

Obrázek výše se pokouší ukázat, že obrácení rolí zarovnáním oblouků stavových diagramů s fázemi zpracování vývojového diagramu.

Vývojový diagram můžete porovnat s montážní linkou ve výrobě, protože vývojový diagram popisuje postup některých úkolů od začátku do konce (např. Transformace vstupu zdrojového kódu na výstup objektového kódu kompilátorem). Stavový automat obecně nemá představu o takovém postupu. Například stavový automat dveří zobrazený v horní části tohoto článku není v pokročilejší fázi, když je ve stavu „zavřeno“ ve srovnání s tím, že je ve stavu „otevřeno“; jednoduše reaguje odlišně na události otevření / zavření. Stav ve stavovém stroji je efektivním způsobem, jak určit konkrétní chování, spíše než fázi zpracování.

Další rozšíření

Zajímavým rozšířením je umožnění toku oblouků z libovolného počtu stavů do libovolného počtu stavů. To má smysl, pouze pokud je povoleno, aby byl systém ve více stavech najednou, což znamená, že jednotlivý stav popisuje pouze podmínku nebo jiný dílčí aspekt celkového, globálního stavu. Výsledný formalismus je znám jako Petriho síť .

Další rozšíření umožňuje integraci vývojových diagramů do státních diagramů Harel. Toto rozšíření podporuje vývoj softwaru, který je založen na událostech i na pracovních postupech.

Viz také

Reference

externí odkazy