Heading

W tych dniach dużo się mówi o Finite State Machines w krainie JavaScript.

Istnieje ta popularna biblioteka zwana XState, z ponad 11000 gwiazdek na GitHubie, na którą ostatnio wpadłem i ciągle czytam o niej na Twitterze i w innych miejscach. To bardzo fajny projekt.

Po raz pierwszy spotkałem Finite State Machines i Automata jeszcze w liceum, 20 lat temu, potem spotkałem je ponownie na moim kursie projektowania cyfrowego na uniwersytecie.

Ten kurs projektowania cyfrowego dotyczył kodowania informacji, algebry boole’a, sieci kombinatorycznych, obwodów sekwencyjnych, sekwencyjnych maszyn stanowych, obwodów arytmetycznych, VHDL i innych.

Znalazłem temat maszyn stanów skończonych zastosowanych w inżynierii frontendowej dość niesamowity, i wróciłem do moich starych książek, aby zobaczyć, czy mogę znaleźć dobre wyjaśnienie ich działania.

Znalazłem wiele informacji, i oczywiście będąc podręcznikami rzeczy są bardziej złożone niż potrzeba (IMHO). Lubię upraszczać rzeczy i zdecydowałem się napisać małe wyjaśnienie dla normalnych ludzi, nie teoretyczne lub cokolwiek zrobione, aby zdać egzamin. Rzeczy, które możesz zastosować w prawdziwym świecie.

Maszyny stanów

Zanim przyjrzę się czym jest maszyna stanów skończonych, chcę najpierw przedstawić czym jest maszyna stanów.

Świat jest wypełniony maszynami stanów. Możesz je zobaczyć wszędzie, ale być może nie myślałeś o nich jako o takich. Po przeczytaniu tego poradnika, jestem pewien, że będziesz wskazywał obiekty w prawdziwym świecie mówiąc do swoich przyjaciół „to jest maszyna stanowa” (w zależności od poziomu nerdostwa twoich przyjaciół).

Najpopularniejszym i najczęściej spotykanym przykładem jest sygnalizacja świetlna.

W dowolnym momencie semafor drogowy ma zdefiniowany stan. Zazwyczaj jest to albo:

• ma włączone zielone światło, a pozostałe 2 światła wyłączone
• ma włączone czerwone światło, a pozostałe 2 światła wyłączone
• jak włączone jest żółte światło, a pozostałe 2 światła wyłączone

(Niektóre semafory są nieco inne, ale nie obchodzi nas to na potrzeby tego przykładu)

W terminologii State Machines, światła włączone lub wyłączone są nazywane wyjściem.

Każdy z tych 3 scenariuszy nazywany jest stanem. Semafor ruchu drogowego zmieni stan, gdy otrzyma dane wejściowe, zazwyczaj jest to ustalony zegar, który decyduje, ile czasu światła powinny być zielone, żółte i czerwone.

Timer w tym przypadku jest wejściem systemu. Niektóre semafory mają przycisk, który pieszy może nacisnąć, aby spowodować wyświetlenie czerwonego światła dla samochodów, i to byłoby kolejne wejście.

W maszynie stanowej, stan może się zmienić (i mamy przejście) tylko w odpowiedzi na wejście.

Skończone maszyny stanów

Maszynę stanów naszych świateł drogowych uważa się za skończoną, ponieważ mamy skończoną liczbę stanów.

Niektóre systemy mogą mieć nieskończoną liczbę stanów.

Na przykład model światowego ekosystemu lub życie owada. Nie możemy tego zdefiniować w skończonej liczbie stanów.

Ale sygnalizacja świetlna? To prosta rzecz i ma 3 stany, jak powiedzieliśmy wyżej.

Jest wiele innych przykładów maszyn stanów skończonych, których moglibyśmy użyć:

• automat vendingowy
• krętacze przy wejściu do metra
• system grzewczy
• zautomatyzowany system metra
• system samojeżdżących samochodów
• windy

Ale pozostańmy przy naszym przykładzie sygnalizacji świetlnej, która jest bardzo prosta i możemy o niej łatwo myśleć.

Modelowanie maszyny stanów

Oczywiście światła drogowe nie istnieją w izolacji. To kolejna maszyna stanów skończonych, która zawiera wiele różnych maszyn stanów skończonych dla każdego urządzenia sygnalizacji świetlnej zainstalowanego po każdej stronie każdej drogi na skrzyżowaniu, które działają synchronicznie.

Nie myślmy o tym teraz. Skupmy się na 1 pojedynczym semaforze drogowym.

Jak powiedzieliśmy wyżej, mamy 3 stany, które możemy nazwać zielony, czerwony, żółty.

Mamy stan początkowy. Powiedzmy, że nasza sygnalizacja świetlna zaczyna się, gdy ją resetujemy, od stanu green.

Mamy timer, który po 50 sekundach stanu zielonego, przesuwa semafor do stanu yellow. Mamy 8 sekund stanu yellow, następnie przechodzimy do stanu red i siedzimy tam przez 32 sekundy, ponieważ ta droga jest drugorzędna i zasługuje na mniej czasu zielonego. Po tym czasie semafor wraca do stanu zielonego i cykl trwa w nieskończoność, aż do momentu, gdy prąd się zatrzyma, a semafor zresetuje się, gdy znów dostanie prąd.

W sumie mamy 90 sekundowy cykl.

Tak możemy to zamodelować:

Możemy to też zamodelować za pomocą tablicy przejść stanów, która pokazuje w jakim stanie jest obecnie maszyna, jakie otrzymuje wejście, jaki jest następny stan i wyjście:

.

Stan	Wejście	Następny stan	Wyjście
Green	Timer 50s	Yellow	Zielona lampka włączona, inne wyłączone
Żółty	Timer 8s	Czerwony	Żółte światło włączone, other off
Red	Timer 32s	Green	Red light on, others off

W naszym prostym przypadku, biorąc pod uwagę dowolny stan maszyny, mamy tylko jeden logiczny stan, do którego możemy przejść, więc tabela i wykres, które zrobiłem, są bardzo, bardzo proste.

Ale kiedy twój system zaczyna być bardziej złożony, bardzo pomocne jest posiadanie takich diagramów i analiz, ponieważ możesz rozumować o swojej aplikacji znacznie łatwiej niż po prostu trzymając wszystko w swojej głowie.

Maszyna stanów skończonych z bardziej złożonymi przejściami stanów

Powyższy przykład jest bardzo prosty. Zamodelujmy teraz inną maszynę stanów skończonych.

Nasz prawdziwy scenariusz jest taki: mamy dom, z jednymi drzwiami, 2 przyciskami i 3 światłami.

W stanie domyślnym wszystkie światła są wyłączone.

Kiedy wchodzimy do domu, możemy nacisnąć jeden z 2 przycisków, które mamy, p1 lub p2. Kiedy naciśniesz któryś z tych przycisków, włączy się l1 światło.

Wyobraź sobie, że jest to światło wejściowe i możesz zdjąć kurtkę. Gdy skończysz, decydujesz, do którego pokoju chcesz wejść (na przykład do kuchni lub sypialni).

Jeśli naciśniesz przycisk p1l1 wyłącza się, a l2 włącza się. Zamiast tego, jeśli naciśniesz przycisk p2l1 wyłącza się i l3 włącza się.

Naciskając kolejny raz dowolny z 2 przycisków, p1 lub p2, lampka, która jest aktualnie włączona wyłączy się, a my wrócimy do stanu początkowego układu.

Ta maszyna stanów skończonych jest nieco bardziej złożona niż pierwsza, ponieważ tym razem możemy mieć wiele tras w zależności od danych wejściowych.

Zamodelujmy to.

Mamy w zasadzie 4 stany:

• brak włączonych świateł
• l1 włączone
• l2 turned on
• l3 turned on

Mamy 2 wejścia:

• p1
• p2

Jeśli zaczniemy od stanu początkowego i spróbujemy zamodelować wszystko, co może się wydarzyć w zależności od tego, jak wejścia są wyzwalane w czasie, to kończymy z:

Co można podsumować za pomocą tej tabeli:

Stan	Wejście	Następny stan
brak włączonych świateł	p1 wciśnięty	l1 włączony
brak włączonych świateł	. p2 wciśnięty	l1 włączony
l1 włączony	p1 wciśnięty	l2 włączony
l1 włączony	p2 wciśnięty	l3 włączony
l2 włączony	p1 wciśnięty	brak świateł turned on
l2 turned on	p2 pressed	no lights turned on
l3 turned on	p1 pressed	no lights turned on
l3 turned on	p2 pressed	no lights turned on

To krótkie i proste wyjaśnienie, ale może to sprawi, że rzeczy „klikną”.

Więcej poradników na temat komputerów:

• Finite State Machines
• System liczb dziesiętnych
• System liczb binarnych
• Konwersja liczb z dziesiętnych na binarne
• Lista drukowalnych znaków ASCII
• Lista znaków nie-drukowalna lista znaków ASCII
• Jak połączyć się z Raspberry Pi za pomocą komputera Mac
• Jak upewnić się, że Raspberry Pi ma zawsze ten sam adres IP
• Bardzo krótkie wprowadzenie do języka COBOL

.