Automat (maszyna stanów) — definicja, automaty skończone i diagramy

Intuicyjne wyjaśnienie

Prostszy, codzienny przykład to automat sprzedający. Gdy wkładamy do niego monety lub pieniądze, maszyna sprawdza, czy otrzymana suma odpowiada cenie produktu. Jeśli tak — akceptuje płatność i wydaje towar; jeśli nie — odrzuca (zwłaszcza fałszywe monety) albo nie wydaje produktu. W tej analogii każdy stan automatu odpowiada np. zgromadzonej kwocie, a otrzymanie monety powoduje przejście do innego stanu.

Podstawowe pojęcia

• Stan — jedno z możliwych „położeń” maszyny; automat może być w jednym stanie na raz.
• Alphabet (alfabet) — zbiór wszystkich dopuszczalnych symboli wejściowych.
• Wejście — sekwencja symboli (słowo) dostarczona automatu; matematycy nazywają pojedynczy element sekwencji symbolem.
• Przejście — reguła mówiąca, do jakiego stanu przejdzie automat po otrzymaniu określonego symbolu w danym stanie.
• Stan początkowy — stan, w którym automat zaczyna przetwarzanie.
• Stany końcowe (akceptujące) — jeśli po przetworzeniu całego wejścia automat znajduje się w jednym z tych stanów, wejście jest akceptowane; w przeciwnym wypadku jest odrzucane.

Formalna definicja automatu skończonego

Automat skończony to struktura zawierająca skończony (policzalny, skończoną) zbiór stanów oraz funkcję przejścia określającą jak automat reaguje na symbole wejściowe. W praktyce wyróżnia się m.in. dwie klasy:

• Deterministyczny automat skończony (DFA) — formalnie opisywany jako piątka (Q, Σ, δ, q0, F), gdzie:
  • Q — skończony zbiór stanów,
  • Σ — alfabet (zbiór symboli wejściowych),
  • δ : Q × Σ → Q — funkcja przejścia (dla każdego stanu i symbolu jest dokładnie jeden następny stan),
  • q0 ∈ Q — stan początkowy,
  • F ⊆ Q — zbiór stanów akceptujących.
• Niedeterministyczny automat skończony (NFA) — podobny opis, lecz funkcja przejścia może zwracać wiele możliwych następnych stanów (δ : Q × (Σ ∪ {ε}) → P(Q)), co oznacza równoczesne „rozgałęzienie” obliczeń; NFA z ε-przejściami dopuszcza przemieszczanie się bez konsumowania symbolu.

Ważne: dla języków formalnych NFA i DFA rozpoznają te same klasy języków (tzw. języki regularne) — każdy NFA ma równoważny DFA, choć ten ostatni może mieć znacznie większą liczbę stanów.

Diagramy stanów (diagramy automatów)

Diagram stanów to graficzna reprezentacja automatu. Zasady rysowania są intuicyjne:

• stany przedstawia się jako okręgi (lub wierzchołki grafu);
• strzałka bez początku lub specjalny znacznik wskazuje stan początkowy;
• stany akceptujące rysuje się podwójną obwódką;
• przejścia oznacza się strzałkami między stanami z etykietami pokazującymi symbol(y) powodujące to przejście (np. 0, 1).

Przykład prostego automatu rozpoznającego słowa nad alfabetem {0,1} zawierające parzystą liczbę jedynek:

• Q = {S_even, S_odd}, q0 = S_even, F = {S_even}.
• Przejścia: ze S_even na S_odd przy symbolu 1; ze S_odd na S_even przy symbolze 1; przy symbolu 0 pozostajemy w tym samym stanie.

Na diagramie S_even i S_odd będą dwoma okręgami, strzałki między nimi oznaczone „1”, a pętle na każdym stanie oznaczone „0”. S_even będzie dodatkowo obwiedziony podwójną kreską (stan akceptujący).

Przykłady zastosowań

• analiza leksykalna w kompilatorach (rozpoznawanie tokenów za pomocą automatów i wyrażeń regularnych),
• modelowanie protokołów i systemów sterowania (maszyny stanów opisują sekwencje zdarzeń i reakcji),
• sprawdzanie poprawności ciągów wejściowych (np. poprawność formatów),
• projektowanie układów cyfrowych i obwodów sterujących,
• silniki wyrażeń regularnych (często wykorzystujące automaty niedeterministyczne z konwersją na deterministyczne lub symulację NFA).

Właściwości i ograniczenia

• Automaty skończone rozpoznają dokładnie języki regularne — mają określone algorytmy i własności (zamknięcie na sumę, concatenation, Kleene star itp.).
• Nie potrafią rozpoznawać języków wymagających pamięci nieskończonej, np. języka {a^n b^n | n ≥ 0} — do tego potrzebna jest np. maszyna ze stosem (pushdown automaton).
• Istnieją algorytmy minimalizacji automatów deterministycznych (np. algorytm Hopcrofta), które redukują liczbę stanów bez zmiany rozpoznawanego języka.
• Pumping lemma jest narzędziem dowodzenia, że dany język nie jest regularny (czyli nie można go rozpoznać za pomocą automatu skończonego).

Inne rodzaje maszyn stanów

• Maszyny Mealy i Moore — rozszerzenia automatów skończonych, które generują wyjście (wartości wyjściowe zależą od stanu i/lub symbolu wejściowego).
• Automaty ze stosem (PDA) — dodają pamięć typu stos i rozpoznają języki bezkontekstowe.
• Maszyny Turinga — modele bardziej wyrafinowane, z nieskończoną taśmą pamięci, służą do badania pojęcia obliczalności.

Podsumowanie

Automat (maszyna stanów) to wygodne i potężne narzędzie służące do modelowania systemów, które reagują na sekwencję zdarzeń lub symboli, przy czym w szczególności automaty skończone — mające skończoną liczbę stanów — są fundamentem teorii języków formalnych i praktycznych zastosowań, takich jak analiza leksykalna czy projektowanie protokołów. Diagram stanów jest prostym i czytelnym sposobem zaprezentowania ich struktury i reguł przejść.