Maszyna stanowa w programowaniu
Wrzesień 29, 2024 | #design-pattern
000010
100000
000001
Koncepcja maszyny stanowej
Maszyna stanowa, znana również jako automat stanowy (ang. state machine), to model matematyczny używany do projektowania systemów logicznych oraz opisu zachowania obiektów dynamicznych.
Choć powyższa definicja brzmi skomplikowanie, kryjąca się za tym podstawowa koncepcja jest dość prosta do zrozumienia. Maszyna stanowa to dowolny program lub urządzenie, które pamięta swój bieżący stan, a następnie reaguje na dane wejściowe zachowując lub zmieniając swój stan na inny.
Prostą maszyną stanową jest szlaban kolejowy, który ma dwa stany - otwarty i zamknięty. W stanie wyjściowym barierka jest podniesiona umożliwiając przejazd samochodom. W chwili zbliżania się pociągu szlaban jest opuszczany aż do osiągnięcia drugiego ze stanów, czyli zablokowania przejazdu. Kiedy pociąg już się oddali następuje powrót do stanu wyjściowego.
Po chwili zastanowienia dojdziemy do wniosku, że świat wokół nas jest pełen maszyn stanowych. Światła drogowe czy bankomaty to urządzenia ale też stojące za nimi oprogramowanie. To także np. algorytmy czy procedury jak proces obsługi klientów w restauracji typu fast-food. Taka maszyna stanowa jest wykorzystywana do organizacji pracy i zapewnienia, że każdy klient jest obsłużony w uporządkowany sposób. Jak widać ten model matematyczny ma powszechne zastosowanie, a jego użycie nie ogranicza się do elektroniki, automatyki czy informatyki. W tym rozumieniu "maszyną" może być urządzenie, oprogramowanie a nawet pojedyncza klasa, albo cokolwiek co zachowuje stan po czym pod wpływem "bodźca" zmienia swój stan w inny.
Podstawowe pojęcia maszyny stanowej
Maszyna stanowa składa się z kilku podstawowych elementów:
Stany (ang. States): Zbiór atrybutów i ich wartości opisujących stan "maszyny".
Przejścia (ang. Transitions): Zmiany stanu, które zachodzą w odpowiedzi na pewne zdarzenia lub warunki. Przejścia mogą wymagać spełnienia określonych warunków, aby zostały zainicjowane i zrealizowane.
Zdarzenia (ang. Events): Czynniki zewnętrzne lub wewnętrzne, które wpływają na zmianę stanów.
Akcje (ang. Actions): Operacje, które są wykonywane w momencie przejścia ze stanu do stanu lub podczas pozostawania w określonym stanie.
Poszczególne pojęcia staną się bardziej przystępne, kiedy zetkniemy się z nimi przy okazji omawiania konkretnych przypadków. W bardziej złożonych maszynach spotkamy się także z innymi pojęciami. Będę je krótko omawiał jak się one mają w stosunku do tych podstawowych kiedy już na nie natrafimy.
Automat Skończony
Pojęcie Maszyna Stanowa jest często używane jako zamiennik dla pojęcia Automat Skończony (ang. Finite State Machine) podczas gdy drugi z wymienionych jest pojęciem węższym ograniczającym się do maszyn stanowych o skończonej liczbie stanów. Ma ona swój stan początkowy a dane wejściowe wyzwalają przejście.
Doskonale obrazuje to realizacja jednej z najbardziej rozpowszechnionych funkcjonalności w internecie, jaką jest pokazywanie i ukrywanie różnych elementów strony www po kliknięciu w nie lub powiązany z nim element.
Implementacja automatu skończonego w JavaScript-cie
Zaimplementowane jako automat skończony ma tylko dwa stany visible i hidden. Stanem początkowym jest drugi z wymienionych. Zdarzeniem jest kliknięcie click, które prowadzi do przejścia obsługiwanego przez funkcję toggleParagraph.
<!DOCTYPE html>
<html lang="pl">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Maszyna Stanowa - Paragraf</title>
</head>
<body>
<button id="toggleButton">Pokaż paragraf</button>
<p id="paragraph" style="display: none;">
To jest przykładowy paragraf, który będzie pokazywany i ukrywany.
</p>
<script>
// Definicja stanów
const states = {
VISIBLE: "visible",
HIDDEN: "hidden"
};
// Inicjalny stan paragrafu
let currentState = states.HIDDEN;
// Pobieranie elementów DOM
const paragraph = document.getElementById("paragraph");
const toggleButton = document.getElementById("toggleButton");
// Funkcja dla akcji: pokaż paragraf
function showParagraph() {
paragraph.style.display = "block";
toggleButton.textContent = "Ukryj paragraf";
}
// Funkcja dla akcji: ukryj paragraf
function hideParagraph() {
paragraph.style.display = "none";
toggleButton.textContent = "Pokaż paragraf";
}
// Funkcja przełączająca stan
function toggleParagraph() {
if (currentState === states.HIDDEN) {
// Przejście do stanu widocznego
currentState = states.VISIBLE;
// Wykonuje akcję "pokaż paragraf"
showParagraph();
} else {
// Przejście do stanu ukrytego
currentState = states.HIDDEN;
// Wykonuje akcję "ukryj paragraf"
hideParagraph();
}
}
// Dodanie zdarzenia kliknięcia do przycisku
toggleButton.addEventListener("click", toggleParagraph);
</script>
</body>
</html>
Deterministyczny i niedeterministyczny automat skończony
Deterministyczny automat skończony
Przykład z pokazywaniem i ukrywaniem paragrafu prowadzi nas też do kolejnego pojęcia jakim jest deterministyczny automat skończony (ang. Deterministic Finite Automaton - DFA).
Co decyduje o tym że funkcja toggleParagraph jest DFA?
O tym, że przełącznik jest DFA decydują jednoznaczne przejścia i przewidywalne zachowanie. Dla każdego stanu i każdego możliwego wejścia (zdarzenia) jest dokładnie jedno określone przejście do innego stanu. W przypadku tej maszyny, kliknięcie przycisku w stanie HIDDEN zawsze prowadzi do stanu VISIBLE, a w stanie VISIBLE zawsze prowadzi do stanu HIDDEN. Nie ma alternatywnych ścieżek. Ponadto wywołanie akcji showParagraph lub hideParagraph zawsze powoduje jednoznaczne i przewidywalne zachowania, bez elementu losowości. W tym modelu maszyna stanu może w danym momencie przyjmować tylko jeden z możliwych stanów.
Niedeterministyczny automat skończony
Przeciwieństwem jest niedeterministyczny automat skończony (ang. NonDeterministic Finite Automaton - NFA). To rodzaj maszyny stanowej, który może znajdować się w wielu stanach naraz i przechodzić do różnych stanów na podstawie tego samego wejścia. Jest to bardziej elastyczny model obliczeń. Niedeterministyczność oznacza, że nie ma jednoznacznych przejść między stanami – dla danego wejścia może istnieć wiele możliwych przejść, a automat wybiera jedno lub kilka równocześnie.
NFA są często wykorzystywane do wyszukiwania wzorców w tekście np. wyrażeń regularnych. Przykładem implementacji takiej maszyny jest klasa do wyszukiwania podatności na iniekcję w zapytaniach SQL
Przykładowa implementacja NFA w języku Python:
import re
class SQLInjectionDetector:
def __init__(self):
# Definiowanie stanów automatu
self.states = {
0: {r"\s*'": [1]}, # rozpoznanie pojedynczego cudzysłowu
1: {r"OR": [2]}, # przejście po wykryciu słowa kluczowego 'OR'
2: {r"1\s*=\s*1": [3], r"\d+\s*=\s*\d+": [3]}, # rozpoznanie '1=1' lub podobnej równości
3: {r"--": [4]}, # wykrycie komentarza
}
self.start_state = 0
self.accept_states = [4]
def is_dangerous(self, query):
# Zaczynamy w stanie początkowym
current_states = [self.start_state]
# Iterujemy przez każdy token w zapytaniu SQL (rozdzielone spacjami)
tokens = query.split()
for token in tokens:
next_states = set()
# Dla każdego aktualnego stanu próbujemy znaleźć pasujące przejścia
for state in current_states:
for pattern, next_state_list in self.states.get(state, {}).items():
if re.match(pattern, token):
# Jeśli dopasowanie się powiedzie, dodajemy wszystkie możliwe stany przejścia
next_states.update(next_state_list)
# Jeśli nie ma możliwych przejść, kontynuujemy z obecnymi stanami
if next_states:
current_states = list(next_states)
else:
continue
# Sprawdzamy, czy którykolwiek z obecnych stanów jest akceptującym
return any(state in self.accept_states for state in current_states)
Przykładowe zapytania SQL do przetestowania
detector = SQLInjectionDetector()
queries = [
"SELECT * FROM users WHERE name = 'admin' OR 1=1 --", # klasyczny atak SQL Injection
"SELECT * FROM products WHERE id = 10", # bezpieczne zapytanie
"SELECT * FROM users WHERE (name = 'test' AND id=34) OR 7=7 --", # inny atak SQL Injection
"SELECT * FROM users WHERE name = 'John'", # bezpieczne zapytanie
]
for query in queries:
if detector.is_dangerous(query):
# Zapytanie potencjalnie niebezpieczne
print(f"WARNING: {query}")
else:
# Zapytanie wydaje się bezpieczne
print(f"OK: {query}")
Wynik
WARNING: SELECT * FROM users WHERE name = 'admin' OR 1=1 --
OK: SELECT * FROM products WHERE id = 10
WARNING: SELECT * FROM users WHERE (name = 'test' AND id=34) OR 7=7 --
OK: SELECT * FROM users WHERE name = 'John'
Powyższa implementacja jest NFA ponieważ:
Równoczesne przetwarzanie wielu stanów:
Używamy listy current_states, która przechowuje wszystkie stany, w których może znajdować się maszyna jednocześnie. Dla każdego tokena przetwarzamy wszystkie możliwe przejścia dla każdego stanu w tej liście. Na podstawie dopasowania wzorca do tokena, możliwe przejścia są dodawane do zbioru next_states.
Przechodzenie między stanami:
Dla każdego tokena sprawdzamy, czy istnieje dopasowanie do wyrażenia regularnego zdefiniowanego w aktualnym stanie. Jeżeli dopasowanie się uda, dodajemy stany przejściowe do next_states. Dzięki temu możliwe jest przetwarzanie wielu ścieżek równocześnie - jeżeli istnieje wiele potencjalnych ścieżek do przetestowania, automat może przetwarzać je równocześnie.
Niedeterministyczne przejścia:
Dla każdego tokena możemy mieć więcej niż jedno przejście, co umożliwia niedeterministyczne przetwarzanie. Na przykład, w stanie 2 dla tokena "1=1", automat przejdzie do stanu 3, ale także dla wzorca \d+\s*=\s*\d+, który rozpoznaje inne liczby, np. 123=123.
Stan akceptujący:
Na końcu sprawdzamy, czy którykolwiek z obecnych stanów jest stanem akceptującym (stan 4), który sygnalizuje, że zapytanie SQL może zawierać próbę SQL Injection.
UWAGA
Stany akceptujące (ang. accepting states lub final states) to specjalne stany w maszynach stanowych, które oznaczają, że maszyna zakończyła swoje działanie w sposób pozytywny. Jeżeli maszyna zakończy swoje przetwarzanie wejścia w stanie akceptującym, oznacza to, że przyjęła (ang. accepted) dany ciąg wejściowy jako poprawny zgodnie z zadanym warunkiem lub wzorcem.
Automat Moore'a i Automat Mealy'ego
Maszyny stanowe można podzielić na dwa główne typy. Automat Moore'a i automat Mealy'ego to dwa rodzaje automatów skończonych (FSM), które różnią się tym, jak generują wyjścia w zależności od stanów i wejść.
Automaty Moore'a
Są często stosowane w systemach sterowania, gdzie wyjście zależy tylko od bieżącego stanu systemu i zmienia się jedynie wtedy, gdy system przechodzi do nowego stanu. Przykładem takiego zastosowania jest sterowanie sygnalizacją świetlną na skrzyżowaniu.
Automat Moore'a dla sygnalizacji świetlnej zmienia stany w określonej kolejności (np. zielone -> żółte -> czerwone), a wyjście (kolor światła) jest przypisane bezpośrednio do każdego stanu. Automat nie zmienia wyjścia w odpowiedzi na bieżące wejście, ale jedynie w odpowiedzi na przejście do innego stanu (np. zmiana stanu w regularnych odstępach czasu).
Opis automatu Moore'a dla sygnalizacji świetlnej:
Stany:
S1: Zielone światło dla drogi A, czerwone dla drogi B.S2: Żółte światło dla drogi A, czerwone dla drogi B.S3: Czerwone światło dla drogi A, zielone dla drogi B.S4: Czerwone światło dla drogi A, żółte dla drogi B.
Wejścia:
Timer: Sygnał zegara, który informuje automat, kiedy należy przejść do następnego stanu (po upływie określonego czasu).
Przejścia między stanami:
S1 -> S2: Po 30 sekundach zielonego światła dla drogi A.S2 -> S3: Po 5 sekundach żółtego światła dla drogi A.S3 -> S4: Po 30 sekundach zielonego światła dla drogi B.S4 -> S1: Po 5 sekundach żółtego światła dla drogi B.
Wyjścia: Każdy stan ma przypisane konkretne wyjście:
S1: Zielone dla drogi A, czerwone dla drogi B.S2: Żółte dla drogi A, czerwone dla drogi B.S3: Czerwone dla drogi A, zielone dla drogi B.S4: Czerwone dla drogi A, żółte dla drogi B.
Implementacja sygnalizacji świetlnej jako automatu Moore'a w Pythonie:
import time
# Definiowanie automatu Moore'a dla sygnalizacji świetlnej
class TrafficLightMoore:
def __init__(self):
# Stany automatu
self.states = {
"S1": {"timer": 30, "output": "Zielone A, Czerwone B", "next": "S2"},
"S2": {"timer": 5, "output": "Żółte A, Czerwone B", "next": "S3"},
"S3": {"timer": 30, "output": "Czerwone A, Zielone B", "next": "S4"},
"S4": {"timer": 5, "output": "Czerwone A, Żółte B", "next": "S1"}
}
self.current_state = "S1" # Stan początkowy
def run(self):
while True:
# Wyjście zależne od bieżącego stanu
print(f"Aktualny stan: {self.current_state}, Wyjście: {self.states[self.current_state]['output']}")
# Czekamy przez określony czas w bieżącym stanie (symulacja działania)
time.sleep(self.states[self.current_state]["timer"])
# Przejście do następnego stanu
self.current_state = self.states[self.current_state]["next"]
# Uruchamianie symulacji sygnalizacji świetlnej
traffic_light = TrafficLightMoore()
traffic_light.run()
Jest to automat Moore'a ponieważ:
Wyjście zależne tylko od stanu: Kolor światła (output) jest zależny wyłącznie od bieżącego stanu (S1, S2, S3 lub S4), a nie od bieżącego wejścia.
Przejścia między stanami są niezależne od wejść: Przejścia między stanami są sterowane przez wewnętrzny zegar (timer), a nie bezpośrednio przez zewnętrzne zdarzenia (np. przycisk lub samochód wjeżdżający na skrzyżowanie).
UWAGA
W przypadku niektórych automatów będących szczególnymi rodzajami maszyn stanowych używa się także pojęć:
Wejścia (ang Inputs ): Wejścia stanowią zdarzenia, które wywołują przejścia między stanami w maszynie stanowej.
Wyjścia (ang Output): Należy je traktować jak akcje czyli operacje wykonywane podczas przebywania w stanie lub przy przejściu.
Zegary (ang Clocks): Służą do monitorowania czasu przebywania w danym stanie i inicjowania przejść po określonym czasie. Są kluczowym elementem automatów z czasowymi ograniczeniami (Timed Automata). Zegary inicjują zdarzenia ale są też elementem przejścia.
Automaty Mealy'ego
Są często stosowane tam, gdzie reakcje systemu muszą być natychmiastowe i zależą zarówno od bieżącego stanu, jak i od natychmiastowego wejścia. Dobrym przykładem praktycznego zastosowania jest system automatycznego naliczania opłat drogowych (ETC, ang. Electronic Toll Collection).
System ETC automatycznie identyfikuje pojazdy na podstawie ich tagów RFID (identyfikatory radiowe) w momencie, gdy pojazd przejeżdża przez bramkę. Na tej podstawie nalicza odpowiednią opłatę lub wykonuje inne operacje, takie jak otwieranie szlabanu.
Kluczowe elementy automatu Mealy'ego dla systemu automatycznego naliczania opłat drogowych:
Stany:
Idle(bezczynność) — system czeka na zbliżenie się pojazdu.VehicleDetected— pojazd został wykryty, następuje identyfikacja.PaymentProcessed— opłata została naliczona lub transakcja została odrzucona.GateOpen— szlaban został otwarty.
Wejścia:
- Identyfikator RFID pojazdu (
vehicleID). - Status płatności (
paymentValid— np.True/False). - Czujnik obecności pojazdu (
vehicleDetected— np.True/False).
- Identyfikator RFID pojazdu (
Wyjścia (reakcje na stan + bieżące wejście):
- Naliczanie opłaty (jeśli pojazd jest zidentyfikowany i płatność jest prawidłowa).
- Otwarcie szlabanu (jeśli opłata została przetworzona).
- Alarm (jeśli pojazd jest niezidentyfikowany lub płatność jest nieprawidłowa).
Implementacja automatu Mealy'ego dla systemu ETC w Pythonie
class ElectronicTollMealy:
def __init__(self):
# Definicja stanów i przejść (stan, wejście -> następny stan, wyjście)
self.transitions = {
("Idle", "vehicleDetected"): ("VehicleDetected", "Scan vehicle RFID"),
("VehicleDetected", "vehicleID_valid"): ("PaymentProcessed", "Process payment"),
("VehicleDetected", "vehicleID_invalid"): ("Idle", "Raise alarm: Invalid vehicle"),
("PaymentProcessed", "paymentValid"): ("GateOpen", "Open gate"),
("PaymentProcessed", "paymentInvalid"): ("Idle", "Raise alarm: Payment failed"),
("GateOpen", "vehiclePasses"): ("Idle", "Close gate"),
}
self.current_state = "Idle" # Stan początkowy
def process_input(self, input_signal):
# Określenie nowego stanu i wyjścia na podstawie bieżącego stanu i wejścia
if (self.current_state, input_signal) in self.transitions:
next_state, output = self.transitions[(self.current_state, input_signal)]
print(f"Stan: {self.current_state} -> {next_state} | Wyjście: {output}")
self.current_state = next_state # Aktualizacja stanu
else:
print(f"Brak przejścia dla stanu: {self.current_state} i wejścia: {input_signal}")
Przykładowe użycie systemu ETC
toll_system = ElectronicTollMealy()
# Symulacja różnych zdarzeń w systemie ETC
input_sequence = [
"vehicleDetected", # Pojazd wykryty
"vehicleID_valid", # Poprawne ID pojazdu
"paymentValid", # Płatność przetworzona poprawnie
"vehiclePasses", # Pojazd przejeżdża przez bramkę
"vehicleDetected", # Kolejny pojazd wykryty
"vehicleID_invalid", # Nieprawidłowe ID pojazdu
"vehicleDetected", # Następny pojazd wykryty
"vehicleID_valid", # Poprawne ID pojazdu
"paymentInvalid", # Błąd w płatności
]
# Przetwarzanie sekwencji wejść
for signal in input_sequence:
toll_system.process_input(signal)
# Result:
# Stan: Idle -> VehicleDetected | Wyjście: Scan vehicle RFID
# Stan: VehicleDetected -> PaymentProcessed | Wyjście: Process payment
# Stan: PaymentProcessed -> GateOpen | Wyjście: Open gate
# Stan: GateOpen -> Idle | Wyjście: Close gate
# Stan: Idle -> VehicleDetected | Wyjście: Scan vehicle RFID
# Stan: VehicleDetected -> Idle | Wyjście: Raise alarm: Invalid vehicle
# Stan: Idle -> VehicleDetected | Wyjście: Scan vehicle RFID
# Stan: VehicleDetected -> PaymentProcessed | Wyjście: Process payment
# Stan: PaymentProcessed -> Idle | Wyjście: Raise alarm: Payment failed
Jest to automat Mealy'ego ponieważ:
Wyjścia zależne od stanu i bieżącego wejścia:
Na przykład, w stanie VehicleDetected wyjście zależy od bieżącego wejścia (vehicleID_valid lub vehicleID_invalid). W zależności od tego, czy ID jest poprawne, automat generuje różne wyjścia (Process payment lub Raise alarm).
Reakcja natychmiastowa na zmianę wejścia:
W automacie Mealy'ego wyjście może się zmieniać natychmiast po zmianie wejścia, bez konieczności przechodzenia do nowego stanu. Przykładem jest stan PaymentProcessed, gdzie natychmiastowe wejście paymentValid lub paymentInvalid wpływa na to, czy system otworzy bramę czy też wygeneruje alarm.
Generowanie wyjścia w trakcie przejścia:
Wyjście jest generowane w trakcie przejścia między stanami (np. przejście z VehicleDetected do PaymentProcessed generuje wyjście Process payment).
Praktyczne zastosowanie automatów Moore'a i Mealy'ego
Automaty Moore'a są idealne do sterowania systemami, gdzie wyjście zależy wyłącznie od bieżącego stanu, a nie od natychmiastowych zmian wejść. Takie systemy są stabilne i przewidywalne, dlatego są szeroko stosowane w aplikacjach czasu rzeczywistego, takich jak:
- sygnalizacja świetlna,
- sterowanie przemysłowe czy sekwencjonowanie operacji w układach cyfrowych.
Automat Mealy'ego jest bardziej odpowiedni do systemów reagujących na zdarzenia w czasie rzeczywistym i wymagających natychmiastowej reakcji na zmiany wejść. Dzięki temu sprawdza się w takich aplikacjach, jak:
- sterowanie systemami bezpieczeństwa (np. wykrywanie i natychmiastowe reagowanie na nieautoryzowany dostęp),
- systemy płatności (automatyczne rozpoznawanie transakcji i reagowanie na ich status),
- kolektory opłat drogowych (natychmiastowa reakcja na wykrycie poprawnej lub niepoprawnej płatności).
Automat z czasowymi ograniczeniami (Timed Automaton)
Automaty z czasowymi ograniczeniami (Timed Automata) są używane w systemach, w których stany muszą się zmieniać w określonych ramach czasowych lub po upływie określonego czasu. Dobrym przykładem zastosowania jest system sterowania drzwiami automatycznymi, który otwiera drzwi, gdy wykryje osobę, utrzymuje je otwarte przez określony czas, a następnie automatycznie je zamyka, jeśli w tym czasie nikt nie przechodzi przez drzwi.
Stany:
Closed: Drzwi są zamknięte.Opening: Drzwi się otwierają.Opened: Drzwi są otwarte.Closing: Drzwi się zamykają.
Przejścia między stanami:
Closed -> Opening: Gdy wykryto osobę.Opening -> Opened: Gdy drzwi są całkowicie otwarte.Opened -> Closing: Gdy licznik czasuT_open> 5 sekund.Closing -> Closed: Gdy drzwi są całkowicie zamknięte.
Zegary:
T_open: Licznik czasu, który zaczyna się odliczać, gdy drzwi są w stanieOpened.
Wejścia:
PersonDetected: Osoba została wykryta.NoMovement: Brak ruchu w pobliżu drzwi.
Wyjścia:
OpenDoor: Rozpoczęcie procesu otwierania drzwi.CloseDoor: Rozpoczęcie procesu zamykania drzwi.
Implementacja Automatu z Czasowymi Ograniczeniami w Pythonie
import time
class TimedDoorAutomaton:
def __init__(self):
# Definicja stanów i przejść
self.states = {
"Closed": {"PersonDetected": ("Opening", "OpenDoor")},
"Opening": {"FullyOpened": ("Opened", None)},
"Opened": {"T_open > 5": ("Closing", "CloseDoor"), "PersonDetected": ("Opened", "ResetTimer")},
"Closing": {"FullyClosed": ("Closed", None)},
}
self.current_state = "Closed" # Stan początkowy
self.timer_open = 0 # Licznik czasu otwarcia
def process_input(self, input_signal):
# Sprawdzamy, czy dla bieżącego stanu i wejścia istnieje przejście
if input_signal in self.states[self.current_state]:
next_state, action = self.states[self.current_state][input_signal]
print(f"Stan: {self.current_state} -> {next_state} | Wyjście: {action}")
self.current_state = next_state # Aktualizacja stanu
return action
else:
print(f"Brak przejścia dla stanu: {self.current_state} i wejścia: {input_signal}")
return None
def run(self):
while True:
if self.current_state == "Opened":
# W stanie "Opened" uruchamiamy licznik czasu
self.timer_open += 1
print(f"Czas otwarcia: {self.timer_open} sekund")
# Symulacja resetowania czasu, jeśli wykryto osobę (osobę wykryto w czasie otwarcia drzwi)
if self.timer_open < 5:
print("Osoba w pobliżu, drzwi pozostają otwarte.")
time.sleep(1)
continue
# Gdy licznik czasu przekroczy 5 sekund, przejście do stanu zamykania
if self.timer_open >= 5:
self.process_input("T_open > 5")
self.timer_open = 0 # Reset licznika czasu
else:
# Oczekiwanie na sygnały wejściowe dla innych stanów
if self.current_state == "Closed":
action = self.process_input("PersonDetected")
if action == "OpenDoor":
self.current_state = "Opening"
print("Drzwi otwierają się...")
time.sleep(1)
elif self.current_state == "Opening":
time.sleep(2) # Symulacja czasu otwierania
self.process_input("FullyOpened")
elif self.current_state == "Closing":
time.sleep(2) # Symulacja czasu zamykania
self.process_input("FullyClosed")
# Uruchomienie symulacji automatu z czasowymi ograniczeniami
door_system = TimedDoorAutomaton()
door_system.run()
Jest to automat z czasowymi ograniczeniami ponieważ:
Przejścia między stanami (Opened -> Closing) zależą od upływu określonego czasu (T_open > 5), co jest charakterystyczne dla automatów czasowych.
Automat stosowy (Pushdown Automaton)
Automaty stosowe są szczególnie użyteczne w przypadkach, gdy wymagane jest śledzenie zagnieżdżonej struktury symboli, takiej jak nawiasy, nawiasy klamrowe, czy rekursywne struktury gramatyczne. Tego typu automaty wykorzystują stos do przechowywania informacji, które pomagają im zarządzać głębokością zagnieżdżenia, co jest niemożliwe do zrealizowania za pomocą zwykłych automatów skończonych. Mają zastosowanie w parserach języków programowania, ale mogą być też użyte do prostszych zadań, takich jak konwersja menu w formacie YAML do HTML.
Stany:
START: Początkowy stan, w którym automat przygotowuje się do przetwarzania.UL_OPENED: Stan po otwarciu znacznika<ul>.LI_OPENED: Stan po otwarciu znacznika<li>.END: Stan końcowy po zakończeniu generowania listy.
Przejścia:
OPEN_UL: Przejście zSTARTlubLI_OPENEDdoUL_OPENED.OPEN_LI: Przejście zUL_OPENEDdoLI_OPENED.CLOSE_UL: Przejście zUL_OPENEDdoLI_OPENEDlubSTART.CLOSE_LI: Przejście zLI_OPENEDdoUL_OPENED.
Zdarzenia:
OPEN_UL,CLOSE_UL,OPEN_LI,CLOSE_LI— wyzwalane podczas przetwarzania elementów YAML w zależności od struktury.Akcje:
htmlOutput.push(): Dodawanie tagów HTML na podstawie aktualnego stanu.stack.push()istack.pop(): Zarządzanie stosowymi elementami, aby śledzić otwarte tagi.
Stos: Służy do śledzenia otwartych i zamkniętych tagów (
ulili), co zapewnia, że zamykanie tagów jest realizowane w odpowiedniej kolejności
Implementacja automatu stosowego w JavaScript, który przekształca strukturę YAML w zagnieżdżoną listę HTML
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>YAML to HTML Menu Parser</title>
<style>
ul {
list-style-type: none;
padding-left: 20px;
}
</style>
</head>
<body>
<div id="menu-container"></div>
<script src="https://cdn.jsdelivr.net/npm/js-yaml@4.1.0/dist/js-yaml.min.js"></script>
<script>
// Przykładowa struktura menu w YAML
const yamlMenu = `
menu:
- label: Home
url: "/"
- label: Products
url: "/products"
submenu:
- label: Electronics
url: "/products/electronics"
submenu:
- label: Smartphones
url: "/products/electronics/smartphones"
- label: Laptops
url: "/products/electronics/laptops"
- label: Clothing
url: "/products/clothing"
submenu:
- label: Men
url: "/products/clothing/men"
- label: Women
url: "/products/clothing/women"
- label: About Us
url: "/about"
- label: Contact
url: "/contact"
`;
// Funkcja konwertująca YAML na HTML za pomocą automatu stosowego
class YamlToHtmlMenuAutomaton {
constructor(yamlData) {
this.stack = []; // Stos do śledzenia otwieranych elementów HTML
this.htmlOutput = []; // Wynikowy ciąg HTML
this.currentState = "START"; // Stan początkowy automatu
this.parsedMenu = jsyaml.load(yamlData); // Parsowanie YAML na obiekt
}
// Metoda przetwarzająca obiekt menu na HTML
processMenu() {
this.processElement(this.parsedMenu.menu); // Przetwarzanie elementów menu głównego
this.transition("END"); // Przejście do stanu końcowego
return this.htmlOutput.join(""); // Zwracanie pełnego ciągu HTML
}
// Rekurencyjna metoda przetwarzająca elementy menu
processElement(element) {
if (Array.isArray(element)) {
this.transition("OPEN_UL"); // Otwórz tag <ul>
element.forEach(item => this.processElement(item)); // Przetwarzanie każdego elementu listy
this.transition("CLOSE_UL"); // Zamknij tag <ul>
} else if (typeof element === "object") {
// Dodanie etykiety i linku dla elementu menu
this.transition("OPEN_LI"); // Otwórz tag <li>
this.htmlOutput.push(`<a href="${element.url}">${element.label}</a>`);
// Jeśli element ma podmenu, przetwarzamy je rekurencyjnie
if (element.submenu) {
this.processElement(element.submenu);
}
this.transition("CLOSE_LI"); // Zamknij tag <li>
}
}
// Funkcja do obsługi przejść między stanami i wykonywania akcji
transition(event) {
switch (this.currentState) {
case "START":
if (event === "OPEN_UL") {
this.htmlOutput.push("<ul>");
this.stack.push("ul");
this.currentState = "UL_OPENED";
}
break;
case "UL_OPENED":
if (event === "OPEN_LI") {
this.htmlOutput.push("<li>");
this.stack.push("li");
this.currentState = "LI_OPENED";
} else if (event === "CLOSE_UL") {
if (this.stack.pop() === "ul") {
this.htmlOutput.push("</ul>");
this.currentState = this.stack.length ? "LI_OPENED" : "START";
}
}
break;
case "LI_OPENED":
if (event === "CLOSE_LI") {
if (this.stack.pop() === "li") {
this.htmlOutput.push("</li>");
this.currentState = "UL_OPENED";
}
} else if (event === "OPEN_UL") {
this.htmlOutput.push("<ul>");
this.stack.push("ul");
this.currentState = "UL_OPENED";
}
break;
case "END":
// Zakończenie przetwarzania
break;
}
}
}
// Inicjalizacja i uruchomienie automatu z YAML
const menuAutomaton = new YamlToHtmlMenuAutomaton(yamlMenu);
const htmlMenu = menuAutomaton.processMenu();
// Wyświetlenie wynikowego menu w kontenerze
document.getElementById("menu-container").innerHTML = htmlMenu;
</script>
</body>
</html>
Wynikiem będzie menu w formacie HTML
<ul>
<li><a href="/">Home</a></li>
<li><a href="/products">Products</a>
<ul>
<li><a href="/products/electronics">Electronics</a>
<ul>
<li><a href="/products/electronics/smartphones">Smartphones</a></li>
<li><a href="/products/electronics/laptops">Laptops</a></li>
</ul>
</li>
<li><a href="/products/clothing">Clothing</a>
<ul>
<li><a href="/products/clothing/men">Men</a></li>
<li><a href="/products/clothing/women">Women</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="/about">About Us</a></li>
<li><a href="/contact">Contact</a></li>
</ul>
Sens stosowania Automatu Stosowego przy parsowaniu struktur hierarchicznych
W strukturze YAML, jak w wielu innych hierarchicznych formatach (np. JSON czy XML), występują zagnieżdżenia — wcięcia lub poziomy, które reprezentują hierarchię danych. Automat stosowy jest idealnym narzędziem do przetwarzania takich struktur, ponieważ:
Stos pozwala śledzić zagnieżdżenia: Gdy napotkamy nowy poziom wcięcia (np. nową podsekcję), możemy dodać do stosu nowy element. Gdy poziom wcięcia maleje (czyli zamykamy sekcję), możemy usunąć element ze stosu.
Stosowanie otwierania i zamykania tagów HTML/XML: Gdy wchodzimy w nową sekcję (np. podsekcję), automatycznie otwieramy nowy tag. Gdy opuszczamy tę sekcję, zamykamy ten tag, zgodnie z zasadą LIFO (Last In, First Out) - otwarty jako ostatni tag jest zamykany jako pierwszy.
UWAGA
W automatach stosowych stos jest strukturą danych, która przechowuje symbole i jest używany do zarządzania zagnieżdżonymi strukturami (np. wyrażenia matematyczne, zagnieżdżone nawiasy). Stos definiuje aktualny kontekst przetwarzania czyli stan (np. śledzenie nawiasów) i akcje związane z dodawaniem/usuwaniem elementów (push/pop).
Maszyna Turinga
Maszyna Turinga (ang. Turing Machine) to teoretyczny model obliczeniowy, który używa taśmy jako nieskończonej pamięci, głowicy do odczytywania i zapisywania symboli na taśmie oraz stanów do śledzenia bieżącej operacji. W praktyce można za jej pomocą symulować każdy algorytm, który można zaimplementować na komputerze. Jest używana jako abstrakcyjne narzędzie w teorii obliczeń do badania problemów obliczalnych i złożoności algorytmicznej. Poniżej przedstawiam przykłady zastosowań maszyn Turinga w różnych kontekstach:
Przykłady użycia maszyny Turinga:
Dodawanie i odejmowanie liczb binarnych: Maszyna Turinga może dodawać, odejmować lub wykonywać inne operacje arytmetyczne na liczbach binarnych, symulując podstawowe operacje arytmetyczne takie jak dodawanie z przeniesieniem lub odejmowanie z pożyczaniem.
Sprawdzanie poprawności nawiasów w wyrażeniach: Maszyna może analizować wyrażenia matematyczne i sprawdzać, czy nawiasy są poprawnie zagnieżdżone (np.
((2 + 3) * (4 - 1))). Jeśli nawiasy są niepoprawnie ułożone (np.((2 + 3) * (4 - 1)), maszyna Turinga może odrzucić takie wyrażenie.Rozpoznawanie palindromów: Maszyna Turinga może sprawdzić, czy dany ciąg znaków jest palindromem, czyli czy czytany od przodu jest taki sam, jak czytany od tyłu (np.
radar,level). W tym przypadku maszyna porównuje symbole z obu końców taśmy, przesuwając się jednocześnie do środka.Sortowanie liczb: Maszyna Turinga może sortować liczby zapisane w ciągu (np. w systemie binarnym). Przykładem jest sortowanie bąbelkowe, gdzie maszyna iteracyjnie przestawia elementy na taśmie, aby uzyskać posortowaną kolejność.
Konwersja między systemami liczbowymi: Maszyna Turinga może być użyta do przekształcania liczb z jednego systemu liczbowego na inny (np. z binarnego na dziesiętny lub z dziesiętnego na system szesnastkowy).
Rozwiązywanie równań algebraicznych: W teorii, maszyna Turinga może być zaprogramowana do rozwiązywania równań algebraicznych, takich jak
ax + b = 0, przekształcając równanie i obliczając wynik na taśmie.Rozpoznawanie gramatyk formalnych: Maszyna Turinga może być zaprogramowana do rozpoznawania określonych gramatyk formalnych (np. języków kontekstowych lub bezkontekstowych). Jest to używane w kompilatorach języków programowania do sprawdzania poprawności składni kodu źródłowego.
Symulacja maszyny Mealy'ego lub Moore'a: Maszyna Turinga może symulować automat skończony (Mealy'ego lub Moore'a), dodając nieskończoną pamięć w postaci taśmy do standardowych maszyn stanowych.
Kompresja danych: Maszyna Turinga może symulować algorytmy kompresji danych, takie jak Huffman lub Lempel-Ziv, przetwarzając wejściowe dane na taśmie i zapisując ich skompresowaną postać.
Symulacja algorytmu Euklidesa: Maszyna Turinga może znaleźć największy wspólny dzielnik (NWD) dwóch liczb za pomocą symulacji algorytmu Euklidesa, wykonując kolejne dzielenia na taśmie.
Generowanie liczb Fibonacciego: Maszyna Turinga może być użyta do generowania ciągu Fibonacciego, iteracyjnie obliczając kolejne liczby na taśmie.
Rozwiązywanie problemów logicznych: Maszyna Turinga może rozwiązywać wyrażenia logiczne, takie jak
AND,OR,XOR, symulując bramki logiczne na taśmie.Sprawdzanie przynależności do języka formalnego: Można użyć maszyny Turinga do sprawdzenia, czy dany ciąg znaków należy do języka formalnego opisanego przez określoną gramatykę.
Rozwiązywanie problemów NP-zupełnych: W teorii, maszyna Turinga może być używana do rozwiązywania problemów NP-zupełnych, takich jak problem komiwojażera, problem plecakowy, czy problem SAT (spełnialności formuł logicznych).
Modelowanie pamięci RAM: Maszyna Turinga może symulować prostą jednostkę RAM, gdzie taśma służy jako pamięć, a głowica pełni rolę wskaźnika.
Rozpoznawanie języków rekurencyjnie przeliczalnych: Maszyna Turinga jest teoretycznym narzędziem do rozpoznawania języków rekurencyjnie przeliczalnych, a także sprawdzania problemów decyzyjnych i przeliczalności.
Symulacja uniwersalnej maszyny Turinga: Można stworzyć maszynę Turinga, która symuluje działanie innych maszyn Turinga. Takie maszyny są nazywane uniwersalnymi maszynami Turinga i są modelem współczesnych komputerów.
Maszyna Turinga może być używana w praktycznie każdym zadaniu obliczeniowym, które można zaimplementować na komputerze. Powyższe przykłady obejmują zarówno operacje matematyczne (dodawanie, odejmowanie, sortowanie), jak i bardziej skomplikowane operacje na językach formalnych (rozpoznawanie gramatyk, sprawdzanie poprawności składni). Maszyny Turinga są kluczowe w badaniach nad teorią obliczeń i stanowią podstawę dla zrozumienia granic obliczalności.
Implementacja Maszyny Turinga w Pythonie do rozpoznawania palindromów
Na podstawie Turing machines in Python
import string
import sys
from enum import Enum
# Definicja stanów maszyny Turinga
class State(Enum):
READ_LEFT = 'q_read_left'
MOVE_RIGHT = 'q_move_right'
CHECK_RIGHT = 'q_check_right'
RETURN_LEFT = 'q_return_left'
ACCEPT = 'q_accept'
REJECT = 'q_reject'
# Definicja ruchów głowicy
class Move(Enum):
LEFT = -1
RIGHT = 1
class TuringMachine:
def __init__(self, tape_list: list):
# Stan początkowy
self.state = State.READ_LEFT
self.write_head = 0
# Dodanie pustego symbolu na końcu taśmy
tape_list.append('#')
self.tape_list = tape_list
self.left_char = None
self.transition_table = {
State.READ_LEFT: [
(lambda: not self._is_end_symbol(), self._read_left_and_move_right_transition),
(self._is_end_symbol, self._complete_transition)
],
State.MOVE_RIGHT: [
(lambda: not self._is_end_symbol(), self._move_right_transition),
(self._is_end_symbol, self._move_right_to_check_transition)
],
State.CHECK_RIGHT: [
(self._is_symbol_match, self._mark_right_symbol_and_move_left_transition),
(lambda: not self._is_symbol_match(), self._brake_transition)
],
State.RETURN_LEFT: [
(lambda: not self._is_end_symbol(), self._move_left_transition),
(self._is_end_symbol, self._move_left_to_read_symbol_transition)
]
}
def get_state(self) -> State:
return self.state
def get_head(self) -> int:
return self.write_head
def get_list(self) -> list:
return self.tape_list
def update_machine(self, character_list):
self.character_list = character_list
# Sprawdzenie dostępnych przejść dla aktualnego stanu
if self.state in self.transition_table:
for checker, transition in self.transition_table[self.state]:
# Sprawdzenie, czy akcja powinna być wykonana
if checker():
# Zastosowanie przejścia
state, move = transition()
self.state = state
self.write_head += move.value
break
def _mark_symbol_as_processed(self):
self.tape_list[self.write_head] = '#'
def _is_end_symbol(self) -> bool:
""" Sprawdzenie, czy głowica jest na przetworzonym symbolu '#' """
return self.tape_list[self.write_head] == '#'
def _is_symbol_match(self) -> bool:
""" Sprawdzenie, czy symbol z prawej strony jest zgodny
z symbolem z lewej strony """
return self.tape_list[self.write_head] == self.left_char or self._is_end_symbol()
def _read_left_and_move_right_transition(self) -> tuple[State, Move]:
""" Czytanie symbolu z lewej strony, zapamiętanie,
oznacanie jako przetworzony i przesunięcie w prawo """
# Oczytanie symbolu z lewej strony
self.left_char = self.tape_list[self.write_head]
# Zmiana symbolu na znacznik przetworzenia
self._mark_symbol_as_processed()
# Przesunięcie w prawo
return State.MOVE_RIGHT, Move.RIGHT
def _complete_transition(self) -> tuple[State, Move]:
""" Przejście do stanu akceptującego gdy
wszystkie symbole są przetworzone """
return State.ACCEPT, Move.RIGHT
def _move_right_transition(self) -> tuple[State, Move]:
""" Kontynuacja przejścia w prawo """
return State.MOVE_RIGHT, Move.RIGHT
def _move_right_to_check_transition(self) -> tuple[State, Move]:
""" Przejście w prawo do sprawdzania symbolu po prawej stronie """
return State.CHECK_RIGHT, Move.LEFT
def _mark_right_symbol_and_move_left_transition(self) -> tuple[State, Move]:
""" Oznaczenie symbolu po prawej stronie jako
przetworzony i przejście w lewo """
self._mark_symbol_as_processed()
return State.RETURN_LEFT, Move.LEFT
def _brake_transition(self) -> tuple[State, Move]:
""" Obsługa niezgodności symboli """
return State.REJECT, Move.LEFT
def _move_left_transition(self) -> tuple[State, Move]:
""" Kontunuacja przejścia w lewo """
return State.RETURN_LEFT, Move.LEFT
def _move_left_to_read_symbol_transition(self) -> tuple[State, Move]:
""" Przejście w lewo do czytania nowego symbolu """
return State.READ_LEFT, Move.RIGHT
def check_palindrome(initial_string):
# Definiowanie zestawu znaków (alfabetu)
character_list = list(string.ascii_lowercase)
character_list.append(' ') # Dodanie spacji jako znaku dozwolonego
# Wydruk ciągu wejściowego
print('Sprawdzanie: ' + initial_string)
print('- - -')
initial_list = list(initial_string)
# Szybkie sprawdzenie, czy wprowadzono dozwolone znaki
for i in initial_list:
if i not in character_list:
print(f'Błąd! Znak >{i}< nie znajduje się w dozwolonej liście znaków!')
sys.exit()
# Inicjalizacja maszyny Turinga
machine = TuringMachine(tape_list=initial_list)
print(machine.get_state(), machine.get_head(), machine.get_list())
# Uruchomienie maszyny z ograniczeniem do 1000 kroków
steps = 0
while machine.get_state() not in [State.ACCEPT, State.REJECT] and steps < 1000:
machine.update_machine(character_list)
print(machine.get_state(), machine.get_head(), machine.get_list())
steps += 1
print('- - -')
# Wynik działania maszyny
if machine.get_state() == State.ACCEPT:
print(f'Ciąg "{initial_string}" jest palindromem! Kroki: {steps}')
else:
print(f'Ciąg "{initial_string}" NIE jest palindromem! Kroki: {steps}')
if __name__ == "__main__":
check_palindrome('oko')
Wynik
Sprawdzanie: oko
- - -
State.READ_LEFT 0 ['o', 'k', 'o', '#']
State.MOVE_RIGHT 1 ['#', 'k', 'o', '#']
State.MOVE_RIGHT 2 ['#', 'k', 'o', '#']
State.MOVE_RIGHT 3 ['#', 'k', 'o', '#']
State.CHECK_RIGHT 2 ['#', 'k', 'o', '#']
State.RETURN_LEFT 1 ['#', 'k', '#', '#']
State.RETURN_LEFT 0 ['#', 'k', '#', '#']
State.READ_LEFT 1 ['#', 'k', '#', '#']
State.MOVE_RIGHT 2 ['#', '#', '#', '#']
State.CHECK_RIGHT 1 ['#', '#', '#', '#']
State.RETURN_LEFT 0 ['#', '#', '#', '#']
State.READ_LEFT 1 ['#', '#', '#', '#']
State.ACCEPT 2 ['#', '#', '#', '#']
- - -
Ciąg "oko" jest palindromem! Kroki: 12
Powyższy kod implementuje maszynę Turinga do sprawdzania, czy podany ciąg znaków jest palindromem. Maszyna symuluje swoje działanie na wejściowej taśmie (tablicy znaków), przechodzi przez różne stany i wykonuje określone przejścia na podstawie aktualnego stanu i symbolu pod głowicą. Program weryfikuje, czy wejściowy ciąg jest palindromem, porównując znaki z lewej strony taśmy z odpowiadającymi im znakami z prawej strony.
Powyższa implementacja odbiega nieco od formalnej Maszyny Turinga z uwagi na "dodatkową pamięć" jaką w tym przypadku jest zmienna left_char przechowująca symbol odczytany po lewej stronie taśmy po to aby go później porównać ze znakiem z prawej strony taśmy. Dzięki temu mamy tylko cztery stany i ograniczoną liczbę przejść (tranzycji). W klasycznej implementacji dla każdego symbolu byłby zdefiniowany osobny status i zestaw przejść. Zaproponowane rozwiązanie jest bardziej złożone ale daje większą elastyczność i modularność. Z drugiej strony odchodzi przez to od klasycznego formalizmu maszyn Turinga, który zakłada jednoznaczność stanów i prostą tablicę przejść.
UWAGA
W maszynie Turinga taśma jest strukturą pamięciową, na której maszyna odczytuje symbole, zapisuje nowe symbole i przesuwa głowicę. Taśma pełni rolę zarówno wejścia (czytanie danych), jak i pamięci wewnętrznej. Głowica na taśmie odczytuje symbole i na podstawie tego zdarzenia, decyduje o przejściu do nowego stanu, a akcje (zapisywanie, przesuwanie głowicy) modyfikują taśmę.
Kiedy już wiemy czym są maszyny stanowe i jakie są ich rodzaje rozpatrzmy w jakich obszarach oprogramowania się je stosuje.
Zastosowanie maszyn stanowych w programowaniu
Maszyny stanowe są fundamentalnym narzędziem w programowaniu, które pomagają w modelowaniu i zarządzaniu złożonymi przepływami logiki oraz procesami, które można rozbić na sekwencje stanów i przejść między nimi. Ich zastosowanie jest szerokie, ponieważ wiele problemów można uprościć do rozpoznawania wzorców, reakcji na zdarzenia, czy sekwencyjnych procesów, które łatwo odwzorować za pomocą stanów.
Przykładowe zastosowania maszyn stanowych:
Systemy reagujące na zdarzenia (Event-Driven Systems): W systemach gdzie stan aplikacji zmienia się na podstawie różnych akcji użytkownika (np. kliknięcia przycisku, wprowadzenia danych w formularzu, odczytanie komunikatu z Kafki), maszyny stanowe są idealnym narzędziem do obsługi tych zdarzeń.
Podobnie w silnikach gier wideo są one wykorzystywane do modelowania zachowań postaci NPC (Non-Player Characters) oraz stanów gry. NPC w grze może mieć stany
idle(bezczynność),walk(chodzenie),attack(atakowanie),flee(uciekanie) i zmieniać je w zależności od sytuacji w grze. W przypadku gier turowych maszyna stanu doskonale nadaje się do organizacji rozgrywki.Kontrolery przepływu (Workflow Controllers): Modelowania przepływów pracy, takich jak przepływy dokumentów, procesy biznesowe czy przepływy w interfejsach użytkownika. Proces składania zamówienia w sklepie internetowym może być reprezentowany jako maszyna stanowa:
koszyk→adres dostawy→płatność→potwierdzenie zamówienia.Parsery języków formalnych: Są podstawą parserów składniowych, które analizują ciągi symboli i sprawdzają, czy są zgodne z określoną gramatyką (np. wyrażenia regularne, analizatory leksykalne, kompilatory).
Automatyczne testowanie oprogramowania: Maszyny stanowe mogą być używane do tworzenia modeli testowych , które automatycznie generują testy pokrywające różne scenariusze (np. testowanie wszystkich możliwych stanów aplikacji). W aplikacjach finansowych można przetestować wszystkie możliwe ścieżki, które przechodzi użytkownik w interfejsie (np. dodawanie i usuwanie transakcji, zmiana waluty).
Interfejsy użytkownika (GUI): W aplikacjach graficznych, ale też działających w konsoli maszyna stanu może służyć do zarządzania różnymi stanami interfejsu (np. stan edycji, stan widoku, stan menu). Edytor tekstu może mieć stany
Normal,Insert,Visual, które kontrolują, jak interfejs reaguje na naciśnięcia klawiszy.Systemy sterowania i automatyzacji: Automaty Mealy'ego i Moore'a są wykorzystywane do projektowania układów logicznych oraz systemów cyfrowych w sprzęcie elektronicznym w sterownikach automatyki przemysłowej (PLC), kontrolerach procesów czy systemach robotyki. Sterowanie pracą windy, która może znajdować się w różnych stanach (
idle,going up,going down,opening doors) i reagować na odpowiednie wejścia.Protokoły komunikacyjne: Maszyny stanowe są stosowane do modelowania protokołów komunikacyjnych, gdzie różne stany reprezentują fazy komunikacji. Protokół HTTP może przejść przez różne stany (np.
SEND_REQUEST,WAIT_RESPONSE,PROCESS_RESPONSE) w zależności od stanu sieci i odpowiedzi serwera.
Dlaczego warto zainteresować się koncepcją maszyn stanowych?
Maszyny stanowe są bardzo intuicyjnym sposobem na modelowanie złożonego zachowania systemu w sposób hierarchiczny. Pomagają wizualizować działanie systemu za pomocą diagramów stanów, co ułatwia ich zrozumienie i debugowanie.
Dobrze zdefiniowane sprawiają, że zachowanie aplikacji jest bardziej przewidywalne. Poszczególne stany są jednoznacznie opisane, a zmiany stanu są wywoływane wyłącznie przez określone zdarzenia. To eliminuje nieoczekiwane zachowania i ułatwia śledzenie błędów.
Pokrycie testami różnych scenariuszy aplikacji jest ułatwione, ponieważ dokładnie wiadomo, w jakim stanie powinna znajdować się maszyna dla danego wejścia. Można stworzyć zestaw testów, który odwzorowuje wszystkie możliwe przejścia w maszynie co zdecydowanie ułatwia testowanie.
Złożoną logikę można łatwo podzielić na mniejsze, niezależne maszyny stanowe, które zarządzają swoimi częściami aplikacji. Jest to szczególnie przydatne w dużych projektach, w których skomplikowane zachowanie może być podzielone na niezależne moduły. Podział logiki na mniejsze moduły ułatwia ich skalowanie i zarządzanie nimi.
Maszyny stanowe umożliwiają klarowne zarządzanie zmianami stanu, które w kodzie proceduralnym lub obiektowym mogą prowadzić do nieoczekiwanych interakcji między różnymi częściami aplikacji. Maszyny stanowe wymuszają jednoznaczne zarządzanie i eliminują niepożądane przejścia.
Koncepcja maszyn stanowych jest uniwersalna - niezależna od języka programowania i może być zastosowana zarówno w systemach embedded, backendowych aplikacjach serwerowych, jak i interfejsach użytkownika.
Dlaczego maszyny stanowe nie zawsze są optymalnym wyborem
Mimo swoich licznych zalet maszyny stanowe, mają również kilka ograniczeń i słabości, które należy uwzględnić podczas ich stosowania w programowaniu. W przypadku bardziej złożonych aplikacji ich użycie może stać się problematyczne, szczególnie jeśli nie są odpowiednio zaprojektowane.
Gdy maszyna stanowa ma zbyt wiele stanów lub też poszczególne stany zależą od wielu wejść, liczba możliwych przejść między nimi rośnie wykładniczo, co sprawia, że zarządzanie staje się skomplikowane. W systemie obsługującym wielowątkowe transakcje finansowe, każda nowa akcja może wymagać modyfikacji kilku przejść i synchronizacji między nimi a w efekcie prowadzić do stanu eksplozji przejść (ang State Transition Explosion) - sytuacji, w której dodanie nowego stanu lub przejścia wymaga modyfikacji wielu części maszyny. Systemy takie są kosztowne w modyfikowaniu i refaktoryzacji
W miarę rozbudowywania aplikacji maszyna stanowa staje się mniej czytelna, zwłaszcza gdy przejścia są rozproszone w wielu miejscach. Utrudnia to zrozumienie ogólnej logiki maszyny, a także jej aktualnego stanu. W dużych projektach wiele stanów i przejść prowadzi do tzw. „spaghetti state machine”, gdzie logika staje się trudna do śledzenia, a debugowanie jest koszmarem. Diagramy stanów stają się trudne do zrozumienia, a kod staje się mniej czytelny i kłopotliwy do utrzymania. Utrudnia to testowanie, identyfikację błędów, śledzenie ścieżek przejść oraz przewidywanie zachowania maszyny.
Klasyczne maszyny stanowe mają problemy z odwzorowaniem bardziej złożonych hierarchii, gdzie stany mogą mieć podstany lub równoległe stany. Użycie płaskiej struktury stanu w złożonych aplikacjach (np. system sterowania z wieloma poziomami, stanami zagnieżdżonymi lub współbieżnymi) prowadzi do bardzo skomplikowanej logiki, którą trudno jest zrozumieć i utrzymywać. Hierarchiczne maszyny stanowe (ang. Hierarchical State Machines - HSM) mogą częściowo rozwiązać ten problem, ale ich implementacja jest bardziej skomplikowana.
Złożone warunki logiczne wymagające współbieżności także są wyzwaniem. Maszyny stanowe są deterministyczne, co oznacza, że obsługa stanów równoległych wymaga dodatkowych konstrukcji, takich jak współbieżne maszyny stanowe lub oddzielne wątki, co komplikuje projekt. Aplikacja sterująca ruchem drogowym, gdzie różne sygnalizacje świetlne muszą działać równocześnie, wymagałaby współbieżnej obsługi maszyn stanowych, a klasyczna maszyna stanowa nie jest w stanie obsłużyć tego scenariusza bez dodatkowych modyfikacji.
Podobnie z obsługą wyjątków czy nieprzewidzianych sytuacji. Awarie sprzętu, przerwania komunikacji, czy też inne błędy wymagają implementacji dodatkowej logiki nie przewidzianej w standardowej koncepcji maszyn stanowych
Podsumowanie:
Reasumując, maszyny stanowe oferują czytelność, łatwość w projektowaniu, predykcyjność oraz silne narzędzia do zarządzania złożonymi zachowaniami aplikacji. Dzięki nim można lepiej organizować kod, zmniejszać ryzyko błędów oraz uzyskać większą elastyczność i rozszerzalność projektów programistycznych. Są potężnym narzędziem, ale ich złożoność rośnie wykładniczo wraz z rozbudową systemu. Są najbardziej efektywne w systemach o ograniczonej liczbie stanów i prostych regułach przejść. Gdy jednak systemy stają się bardziej złożone, warto rozważyć inne podejścia lub łączenie maszyn stanowych z innymi paradygmatami (np. logika zdarzeń, programowanie reaktywne), aby radzić sobie z wyzwaniami związanymi z nadmierną liczbą stanów i przejść.
Perturbacje