Szukam dobrych przykładów skończonych maszyn stanów; język nie jest szczególnie ważny, tylko dobre przykłady.

Implementacje kodu są przydatne (pseudo-kod uogólniony), ale bardzo przydatne jest również gromadzenie różnych zastosowań FSM.

Przykłady niekoniecznie muszą być oparte na komputerze, na przykład przykład sieci kolejowej Mike'a Dunlavey'a jest bardzo przydatny.

Sejf (wywołane zdarzenie)

• Stany : Wiele stanów „zablokowanych”, jeden „odblokowany”
• Przejścia : Prawidłowe kombinacje / klucze przenoszą cię z początkowych stanów zablokowanych do stanów zablokowanych bliżej odblokowanych, aż w końcu odblokujesz. Niepoprawne kombinacje / klucze powodują powrót do początkowego stanu zablokowania (czasami nazywanego bezczynnością) .

Sygnalizacja świetlna (wyzwolony czas | czujnik [zdarzenie] wyzwolony)

• Stany : CZERWONY, ŻÓŁTY, ZIELONY (najprostszy przykład)
• Przejścia : po upływie czasu zmień CZERWONY na ZIELONY, ZIELONY na ŻÓŁTY i ŻÓŁTY na CZERWONY. Może być również wyzwalany przez wykrywanie samochodów w różnych (bardziej skomplikowanych) stanach.

Automat (aktywacja zdarzenia, odmiana sejfu )

• Stany : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS itp., VEND, CHANGE
• Przejścia : zmiany stanu po włożeniu monet, rachunków, przejście do VEND po prawidłowej kwocie zakupu (lub więcej), a następnie przejście do ZMIANY lub JUŻ (w zależności od tego, jak etyczny jest Twój automat)

Przykład protokołu bramki granicznej

BGP to protokół, który wspiera kluczowe decyzje dotyczące routingu w Internecie. Utrzymuje tabelę, aby określić dostępność hostów z danego węzła, i sprawiła, że ​​Internet był naprawdę zdecentralizowany.

W sieci każdy węzeł BGP jest równorzędny i używa skończonej maszyny stanów, z jednym z sześciu stanów: Bezczynności , Połącz , Aktywny , OpenSent , OpenConfirm i Ustalony . Każde połączenie równorzędne w sieci utrzymuje jeden z tych stanów.

Protokół BGP określa komunikaty wysyłane do peerów w celu zmiany ich stanu.

Wykres statystyk BPG.

Bezczynny

Pierwszy stan Bezczynny . W tym stanie BGP inicjuje zasoby, odrzuca próby połączenia przychodzącego i inicjuje połączenie z peerem.

Połączyć

Drugi stan Połącz . W tym stanie router czeka na zakończenie połączenia i jeśli zakończy się powodzeniem, przejdzie w stan OpenSent . Jeśli się to nie powiedzie, resetuje licznik ConnectRetry i po wygaśnięciu przechodzi w stan Aktywny .

Aktywny

W stanie Aktywnym router resetuje licznik ConnectRetry na zero i powraca do stanu Połącz .

OpenSent

W stanie OpenSent router wysyła wiadomość Open i czeka na jedną w zamian. Komunikaty podtrzymujące są wymieniane, a po pomyślnym odebraniu router jest przełączany w stan Ustanowiony .

Ustanowiony

W stanie Ustanowiony router może wysyłać / odbierać: Keepalive; Aktualizacja; oraz wiadomości z powiadomieniem do / od swojego partnera.

Więcej informacji o BGP znajduje się na wikipedii

Są przydatne do modelowania wszelkiego rodzaju rzeczy. Na przykład cykl wyborczy można modelować z państwami na wzór (normalnego rządu) - wyborów zwanych -> (wczesna kampania) - Parlament rozwiązany -> (ciężka kampania) - wybory -> (liczenie głosów ). Następnie albo (liczenie głosów) - brak większości -> (negocjacje koalicyjne) - osiągnięto porozumienie -> (normalny rząd) lub (liczenie głosów) - większość -> (normalny rząd). Zaimplementowałem wariant tego schematu w grze z podgrą polityczną.

Są one również wykorzystywane w innych aspektach gier: AI często zależy od stanu; przejścia między menu i poziomami oraz przejścia po śmierci lub ukończeniu poziomu są często dobrze modelowane przez FSM.

Parser CSV używany we wtyczce jquery-csv

Jest to podstawowy parser gramatyki Chomsky'ego typu III .

Tokenizator wyrażeń regularnych służy do oceny danych według char-by-char. Po napotkaniu znaku sterującego kod jest przekazywany do instrukcji switch w celu dalszej oceny w oparciu o stan początkowy. Znaki niekontrolowane są grupowane i kopiowane masowo, aby zmniejszyć liczbę wymaganych operacji kopiowania ciągów.

Tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

Pierwszy zestaw dopasowań to znaki sterujące: separator wartości („) separator wartości (,) i separator wprowadzania (wszystkie odmiany znaku nowej linii). Ostatnie dopasowanie obsługuje grupowanie znaków niekontrolowanych.

Analizator składni musi spełniać 10 reguł:

• Reguła # 1 - Jeden wpis na linię, każda linia kończy się nową linią
• Reguła # 2 - Końcowy znak nowej linii na końcu pliku został pominięty
• Reguła # 3 - Pierwszy wiersz zawiera dane nagłówka
• Reguła # 4 - Spacje są traktowane jako dane, a wpisy nie powinny zawierać przecinka końcowego
• Reguła # 5 - Linie mogą, ale nie muszą być ograniczone podwójnymi cudzysłowami
• Reguła # 6 - Pola zawierające podział wiersza, podwójne cudzysłowy i przecinki powinny być ujęte w cudzysłowy
• Reguła # 7 - Jeśli do zamykania pól stosuje się podwójne cudzysłowy, wówczas cytat pojawiający się w polu musi być poprzedzony innym podwójnym cudzysłowem
• Poprawka nr 1 - Pole nienotowane może lub może
• Poprawka nr 2 - Cytowane pole może, ale nie musi
• Poprawka nr 3 - Ostatnie pole we wpisie może zawierać wartość zerową lub nie

Uwaga: 7 najlepszych reguł pochodzi bezpośrednio z IETF RFC 4180 . Ostatnie 3 zostały dodane, aby objąć przypadki krawędzi wprowadzone przez nowoczesne aplikacje arkuszy kalkulacyjnych (np. Excel, Arkusz kalkulacyjny Google), które domyślnie nie ograniczają (tj. Cytują) wszystkich wartości. Próbowałem przyczynić się do zmian w RFC, ale jeszcze nie usłyszałem odpowiedzi na moje zapytanie.

Wystarczy z podsumowaniem, oto schemat:

Stany:

1. stan początkowy dla wpisu i / lub wartości
2. napotkano cytat otwierający
3. napotkano drugi cytat
4. napotkano niecytowaną wartość

Przejścia:

• za. sprawdza zarówno wartości cytowane (1), wartości niecytowane (3), wartości zerowe (0), wpisy zerowe (0) i nowe wpisy (0)
• b. sprawdza drugi znak zapytania (2)
• do. sprawdza, czy istnieje cytat (1), koniec wartości (0) i koniec wpisu (0)
• re. sprawdza koniec wartości (0) i koniec wpisu (0)

Uwaga: w rzeczywistości brakuje stanu. Powinien znajdować się wiersz od „c” -> „b” oznaczony stanem „1”, ponieważ drugi znak delimitera oznacza, że ​​pierwszy separator jest nadal otwarty. W rzeczywistości prawdopodobnie lepiej byłoby przedstawić ją jako kolejne przejście. Ich tworzenie jest sztuką, nie ma jednego poprawnego sposobu.

Uwaga: Brakuje również stanu wyjścia, ale przy prawidłowych danych analizator zawsze kończy się na przejściu „a” i żaden ze stanów nie jest możliwy, ponieważ nie ma już nic do przeanalizowania.

Różnica między stanami a przejściami:

Stan jest skończony, co oznacza, że ​​można go wywnioskować tylko z jednej rzeczy.

Przejście reprezentuje przepływ między stanami, więc może oznaczać wiele rzeczy.

Zasadniczo relacja stan-> przejście wynosi 1 -> * (tj. Jeden do wielu). Państwo definiuje „co to jest”, a przejście określa „jak sobie z tym poradzić”.

Uwaga: Nie martw się, jeśli zastosowanie stanów / przejść nie jest intuicyjne, nie jest intuicyjne. Zajęło mi trochę obszernej korespondencji z kimś znacznie mądrzejszym ode mnie, zanim w końcu udało mi się utrzymać koncepcję.

Pseudokod:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Uwaga: To jest sedno, w praktyce jest o wiele więcej do rozważenia. Na przykład sprawdzanie błędów, wartości zerowe, końcowa pusta linia (tj. Która jest poprawna) itp.

W tym przypadku stan jest warunkiem rzeczy, gdy blok dopasowania wyrażenia regularnego kończy iterację. Przejście jest reprezentowane jako instrukcje przypadku.

Jako ludzie mamy tendencję do uproszczenia operacji niskiego poziomu do wyższego poziomu, ale streszczenia pracy z FSM jest praca z operacji niskim poziomie. Podczas gdy poszczególne stany i przejścia są bardzo łatwe do indywidualnej pracy, z natury trudno jest zobrazować całość naraz. Odkryłem, że najłatwiej jest podążać w kółko poszczególnymi ścieżkami wykonania, dopóki nie mogłem zrozumieć, jak przebiegają przejścia. Jest królem nauki matematyki, nie będziesz w stanie oceniać kodu z wyższego poziomu, dopóki szczegóły niskiego poziomu nie staną się automatyczne.

Poza tym: jeśli spojrzysz na faktyczną implementację, brakuje wielu szczegółów. Po pierwsze, wszystkie niemożliwe ścieżki spowodują określone wyjątki. Uderzenie ich nie powinno być możliwe, ale jeśli coś się zepsuje, absolutnie wyzwolą wyjątki w teście. Po drugie, reguły parsera dotyczące dozwolonego ciągu „legalnego” łańcucha danych CSV są dość luźne, więc kod potrzebny do obsługi wielu konkretnych przypadków krawędzi. Niezależnie od tego był to proces wyśmiewania FSM przed wszystkimi poprawkami błędów, rozszerzeniami i dostrajaniem.

Jak w przypadku większości projektów, nie jest to dokładna reprezentacja implementacji, ale przedstawia najważniejsze części. W praktyce z tego projektu pochodzą 3 różne funkcje analizatora składni: rozdzielacz linii specyficzny dla csv, analizator jednowierszowy i kompletny analizator składający się z wielu linii. Wszystkie działają w podobny sposób, różnią się sposobem obsługi znaków nowej linii.

Prosty FSM w Javie

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Proszę bardzo. OK, to nie jest genialne, ale pokazuje pomysł.

Często można znaleźć FSM w produktach telekomunikacyjnych, ponieważ oferują one proste rozwiązanie skomplikowanej sytuacji.

Odkryłem, że myślenie / modelowanie windy (windy) jest dobrym przykładem skończonej maszyny stanów. Nie wymaga wiele od wprowadzenia, ale zapewnia daleki od trywialnej sytuacji do wdrożenia.

Stany znajdują się na przykład na parterze, na pierwszym piętrze itp. I przenoszą ziemię na pierwsze piętro lub przenoszą trzecią na parter, ale obecnie między piętrem 3 a 2 i tak dalej.

Działanie przycisków w klatce windowej i na samych podłogach zapewnia dane wejściowe, których działanie zależy zarówno od naciśnięcia przycisku, jak i od bieżącego stanu.

Każde piętro, z wyjątkiem górnej i dolnej, będzie miało dwa przyciski: jeden z prośbą o windę, aby wejść w górę, a drugi o dół.

OK, oto przykład. Załóżmy, że chcesz przeanalizować liczbę całkowitą. Poszłoby mniej więcej tak, dd*gdzie djest liczba całkowita.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Oczywiście, jak powiedział @Gary, można je ukryć gotoza pomocą instrukcji switch i zmiennej stanu. Zauważ, że można utworzyć strukturę tego kodu, który jest izomorficzny w stosunku do pierwotnego wyrażenia regularnego:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Oczywiście możesz to również zrobić za pomocą tabeli odnośników.

Maszyny stanów skończonych można tworzyć na wiele sposobów, a wiele rzeczy można opisać jako instancje maszyn stanów skończonych. To nie tyle „koncepcja”, co koncepcja, do myślenia o rzeczach.

Przykład sieci kolejowej

Jednym z przykładów FSM jest sieć kolejowa.

Istnieje skończona liczba zwrotnic, w których pociąg może jechać na jeden z dwóch torów.

Istnieje ograniczona liczba ścieżek łączących te przełączniki.

W dowolnym momencie pociąg znajduje się na jednym torze, można go wysłać na inny tor, przekraczając przełącznik, w oparciu o pojedynczy bit informacji wejściowych.

Maszyna stanów skończonych w Rubim:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Takie jest zachowanie pojedynczego węzła obliczeniowego w systemie rozproszonym, ustanawiając schemat komunikacji oparty na łączu. Mniej więcej. W formie graficznej wygląda to tak:

Sprawdź ten link, aby uzyskać kilka prostych przykładów analizy leksykalnej (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Możesz także sprawdzić przykłady „książeczki smoków” (nie jest to lekka lektura)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

W praktyce maszyny stanowe są często używane do:

• Cele projektowe (modelowanie różnych działań w programie)
• Parsery języka naturalnego (gramatyki)
• Przetwarzanie ciągu

Jednym z przykładów może być automat stanów, który skanuje ciąg znaków, aby sprawdzić, czy ma właściwą składnię. Na przykład holenderskie kody pocztowe mają format „1234 AB”. Pierwsza część może zawierać tylko cyfry, druga tylko litery. Można napisać automat stanowy, który śledzi, czy jest w stanie NUMEROWY, czy w stanie LITEROWYM, a jeśli napotka nieprawidłowe wejście, odrzuć go.

Ta maszyna stanów akceptora ma dwa stany: numeryczny i alfa. Automat stanowy uruchamia się w stanie numerycznym i zaczyna odczytywać znaki ciągu do sprawdzenia. Jeśli napotkane zostaną nieprawidłowe znaki w którymkolwiek ze stanów, funkcja zwraca wartość False, odrzucając dane wejściowe jako nieprawidłowe.

Kod Python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Źródło: (skończone) maszyny państwowe w praktyce