Konstrukcja struktury danych FSM

Question

Chcę napisać FSM, który zaczyna się od stanu bezczynności i przechodzi z jednego stanu do drugiego na podstawie jakiegoś zdarzenia. Nie znam kodowania FSM, a Google go nie pomógł. Doceń, jeśli ktoś może opublikować strukturę danych C, która mogłaby zostać użyta do tego samego.

Dzięki, syuga2012

Answer 1

Zobacz Wikipedia do formalnej definicji. Musisz wybrać swój zestaw stanów: S, Twój alfabet wejściowy Σ i twoja funkcja przejścia δ. Najprostszym reprezentacja jest mieć S jest zbiór liczb 0, 1, 2, ..., N1, gdzie N jest liczbą stanów i Σ jako zbiór liczb całkowitych 0, 1, 2, ..., M1, gdzie M oznacza liczbę wejść i δ jest tak duża N przez M matrycy. Na koniec można zapisać zbiór stanów akceptujących, przechowując tablicę bitów N, gdzie bit th ma wartość 1, jeśli stan 01 jest stanem akceptującym, lub 0, jeśli nie jest stanem akceptacji .

Na przykład, tutaj jest FSM na rysunku 3 z artykułu z Wikipedii:

#define NSTATES 2 
#define NINPUTS 2 
const int transition_function[NSTATES][NINPUTS] = {{1, 0}, {0, 1}}; 
const int is_accepting_state[NSTATES] = {1, 0}; 

int main(void) 
{ 
    int current_state = 0; // initial state 
    while(has_more_input()) 
    { 
     // advance to next state based on input 
     int input = get_next_input(); 
     current_state = transition_function[current_state][input]; 
    } 

    int accepted = is_accepting_state[current_state]; 
    // do stuff 
} 

Answer 2

Można w zasadzie używać „if” warunkowy i zmienna do przechowywania aktualny stan FSM.

Na przykład (tylko koncepcja):

int state = 0; 
while((ch = getch()) != 'q'){ 
    if(state == 0) 
     if(ch == '0') 
      state = 1; 
     else if(ch == '1') 
      state = 0; 
    else if(state == 1) 
     if(ch == '0') 
      state = 2; 
     else if(ch == '1') 
      state = 0; 
    else if(state == 2) 
    { 
     printf("detected two 0s\n"); 
     break; 
    } 
} 

Dla bardziej wyrafinowanych realizacji, można rozważyć sklep stan przejściowy w tablicy dwa wymiary:

int t[][] = {{1,0},{2,0},{2,2}}; 
int state = 0; 

while((ch = getch()) != 'q'){ 
    state = t[state][ch - '0']; 
    if(state == 2){ 
     ... 
    } 
} 

Answer 3

jeśli przez FSM znaczy automat skończony , i podoba ci się to w prosty sposób, użyj wyliczeń, aby nadać swoim państwom nazwę i przełącz się między nimi.

W przeciwnym razie użyj funktorów. możesz przejrzeć fantazyjną definicję w dokumentach STL lub DOBRO.

Są to mniej lub więcej obiekty, które mają metodę, np. . o nazwie run(), która wykonuje wszystko, co powinno być zrobione w tym stanie, z tą przewagą, że każdy stan ma własny zasięg .

Answer 4

Mamy wdrożony automat skończony dla firm telekomunikacyjnych w przeszłości i zawsze stosować tablicę struktur, wstępnie wypełnione jak:

/* States */ 
#define ST_ANY 0 
#define ST_START 1 
: : : : : 

/* Events */ 
#define EV_INIT 0 
#define EV_ERROR 1 
: : : : : 

/* Rule functions */ 
int initialize(void) { 
    /* Initialize FSM here */ 
    return ST_INIT_DONE 
} 
: : : : : 

/* Structures for transition rules */ 
typedef struct { 
    int state; 
    int event; 
    (int)(*fn)(); 
} rule; 
rule ruleset[] = { 
    {ST_START, EV_INIT, initialize}, 
    : : : : : 
    {ST_ANY, EV_ERROR, error}, 
    {ST_ANY, EV_ANY, fatal_fsm_error} 
}; 

może mam wskaźnik funkcji fn deklarowaną źle ponieważ jest to z pamięci . Zasadniczo maszyna stanu przeszukała tablicę pod kątem odpowiedniego stanu i zdarzenia i wywołała funkcję, która zrobiła to, co trzeba było zrobić, a następnie zwróciła nowy stan.

Określone stany zostały wprowadzone jako pierwsze, a wpisy ST_ANY jako ostatnie, ponieważ priorytet reguł zależał od ich pozycji w tablicy. Pierwsza zasada, która została znaleziona, była używana.

Ponadto pamiętam, że mieliśmy zestaw indeksów do pierwszej reguły dla każdego stanu, aby przyspieszyć wyszukiwanie (wszystkie reguły o tym samym stanie początkowym zostały zgrupowane).

Należy również pamiętać, że był to czysty C - może być lepszy sposób na zrobienie tego za pomocą C++.

Answer 5

Kilka osób z AT & T, obecnie w Google, napisało jedną z najlepszych bibliotek FSM do powszechnego użytku. Sprawdź to tutaj, nazywa się OpenFST.

Jest szybka, wydajna i stworzyła bardzo przejrzysty zestaw operacji, które można wykonać na FSM, aby zminimalizować je lub określić, aby były jeszcze bardziej przydatne w rzeczywistych problemach.

Answer 6

Skończona maszyna stanów składa się ze skończonej liczby dyskretnych stanów (wiem, pedantyczny, ale wciąż), które ogólnie mogą być reprezentowane jako wartości całkowite. W c lub C++ używanie wyliczenia jest bardzo powszechne.

Maszyna odpowiada na skończoną liczbę wejść, które często mogą być reprezentowane inną zmienną o wartości całkowitej. W bardziej skomplikowanych przypadkach można użyć struktury reprezentującej stan wejściowy.

Każda kombinacja stanu wewnętrznego i zewnętrznego wejścia powoduje, że urządzenie do:

1. ewentualnie przejścia do innego stanu
2. może wygenerować wyjście

prosty przypadek C może wyglądać jak ten

choć jest to trudne do odczytania i można go łatwo podzielić na wiele funkcji, na przykład:

while (state != STOP_STATE){ 
    int input = GetInput(); 
    switch (state) { 
    case IDLE_STATE: 
     state = DoIdleState(input); 
     break; 
    // .. 
    }; 
    }; 

ze złożonością każdego stanu w jego własnej funkcji.

Jako m3rLinEz says możesz przechodzić przejścia w tablicy w celu szybkiego indeksowania. Możesz także przytrzymać wskaźnik funkcyjny w tablicy, aby skutecznie poradzić sobie z fazą działania. Jest to szczególnie przydatne do automatycznego generowania dużych i złożonych maszyn stanu.

Answer 7

Odpowiedzi tutaj wydają się bardzo skomplikowane (ale dokładne, niemniej jednak.) Więc oto moje myśli.

Po pierwsze, podoba mi się dmckee (operacyjna) definicja FSM i ich zastosowanie do programowania.

ma także automat skończony składa się skończonej skończonej liczbie stanów ( znam pedantic, ale), które mogą ogół reprezentowane jako liczba całkowita wartości. W c lub C++ przy użyciu wyliczenia jest bardzo powszechne.

Urządzenie odpowiada na skończoną liczbę wejść , która często może być reprezentowana przez inną zmienną o wartości całkowitej . W bardziej skomplikowanych przypadkach można użyć struktury do reprezentującej stan wejścia.

Każda kombinacja stanu wewnętrznego i wejścia zewnętrznego spowoduje maszynę do:

1. ewentualnie przejście do innego stanu
2. ewentualnie wygenerować jakiś wynik

więc masz program. Ma stany i jest ich skończona liczba. ("żarówka jest jasna" lub "żarówka jest słaba" lub "żarówka jest wyłączona." 3 stany skończone.) Twój program może być tylko w jednym stanie na raz.

Powiedzmy, że chcesz, aby twój program zmieniał stany. Zazwyczaj będziesz potrzebować czegoś, aby stało, aby wywołać zmianę stanu. W tym przykładzie, w jaki sposób możemy wziąć dane wejściowe użytkownika, aby określić stan - powiedzmy, naciśnij klawisz.

Możesz chcieć takiej logiki. Gdy użytkownik naciśnie klawisz:

1. Jeśli żarówka jest "wyłączona", należy ją "przyciemnić".
2. Jeśli żarówka jest "słaba", żarówka powinna być "jasna".
3. Jeśli żarówka jest "jasna", włącz żarówkę "off".

Oczywiście, zamiast "zmieniać żarówkę", można "zmieniać kolor tekstu" lub cokolwiek program ten musi wykonać. Zanim zaczniesz, będziesz chciał zdefiniować swoje stany.

Więc patrząc na niektóre kodu pseudoish C:

/* We have 3 states. We can use constants to represent those states */ 
#define BULB_OFF 0 
#define BULB_DIM 1 
#define BULB_BRIGHT 2 

/* And now we set the default state */ 
int currentState = BULB_OFF; 

/* now we want to wait for the user's input. While we're waiting, we are "idle" */ 
while(1) { 
    waitForUserKeystroke(); /* Waiting for something to happen... */ 

    /* Okay, the user has pressed a key. Now for our state machine */ 

    switch(currentState) { 
     case BULB_OFF: 
     currentState = BULB_DIM; 
     break; 
     case BULB_DIM: 
     currentState = BULB_BRIGHT; 
     doCoolBulbStuff(); 
     break; 
     case BULB_BRIGHT: 
     currentState = BULB_OFF; 
     break; 
    } 
} 

I voila. Prosty program, który zmienia stan.

Ten kod wykonuje tylko niewielką część instrukcji switch - w zależności od bieżącego stanu bieżącego. Następnie ten stan jest aktualizowany. Tak działają FSM.

Teraz oto kilka rzeczy, które możesz zrobić:

1. Oczywiście, ten program po prostu zmienia zmienną currentState. Będziesz chciał, aby twój kod zrobił coś bardziej interesującego przy zmianie stanu. Funkcja doCoolBulbStuff() może, nie wiem, umieścić zdjęcie żarówek na ekranie. Lub coś.

2. Ten kod wyszukuje tylko naciśnięcie klawisza. Ale twój FSM (a tym samym twoja instrukcja przełączania) może wybrać stan w oparciu o to, co użytkownik wprowadził (np. "O" oznacza "idź do wyłączenia", a nie po prostu przejdź do następnego elementu w sekwencji.)

Część pytania dotyczyła struktury danych.

Jedna osoba zasugerowała użycie enum do śledzenia stanów. Jest to dobra alternatywa dla #defines, której użyłem w moim przykładzie. Ludzie sugerują również tablice - i te tablice śledzą przejścia między stanami. Jest to również doskonała struktura do użycia.

Biorąc pod uwagę powyższe, można użyć dowolnej struktury (coś podobnego do drzewa, tablicy, czegokolwiek), aby śledzić poszczególne stany i określić, co należy zrobić w każdym stanie (stąd niektóre sugestie użyj "wskaźników funkcji" - mapuj stan do wskaźnika funkcji, który wskazuje, co zrobić w tym stanie.)

Nadzieję, że pomaga!