Структура структуры данных FSM

Question

Я хочу написать FSM, который начинается с состояния бездействия и переходит из одного состояния в другое на основе какого-либо события. Я не знаком с кодированием FSM, и Google не помог. Цените, если кто-то может опубликовать структуру данных C, которая может быть использована для нее.

Спасибо, syuga2012

Answer 1

См Wikipedia для формального определения. Вам необходимо принять решение о вашем штате S, ваш вводный алфавит Σ и ваша функция перехода δ. Простейшее представление должно иметь S множество целых чисел 0, 1, 2, ..., N -1, где N является число состояний, а также для Σ множество целых чисел 0, 1, 2, ..., М -1, где М это количество входов, а затем δ просто большой N от M матрицы. Наконец, вы можете сохранить набор принимающих состояний, сохранив массив из N бит, где бит i-й бит равен 1, если i-го состояния является принимающим состоянием или 0, если оно не является принимающим состоянием ,

Например, вот в FSM на рисунке 3 статьи Википедии:

#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

Вы можете в основном использовать «если» условно и переменная для хранения текущего состояния автомата.

Например (только концепция):

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; 
    } 
} 

Для более сложной реализации, вы можете рассмотреть магазин переходного состояния в два двухмерного массива:

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

если по FSM вы имеете в виду конечный автомат , , и вам это нравится просто, используйте перечисления, чтобы называть ваши штаты и переключаться между ними.

В противном случае используйте функторы. вы можете посмотреть причудливое определение в документах stl или boost.

Это более или менее объекты, имеющие метод , например. вызываемый run(), который выполняет все, что должно быть сделано в этом состоянии, с тем преимуществом, что каждое состояние имеет свой собственный размер .

Answer 4

Мы реализовали конечный автомат для телекоммуникационных компаний в прошлом и всегда использовали массив структур, предварительно заполненные как:

/* 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} 
}; 

I может иметь функцию указатель fn объявленные неправильно, поскольку это из памяти , В основном конечный автомат искал массив для соответствующего состояния и события и называл функцию, которая делала то, что должно было быть сделано, а затем возвращала новое состояние.

Конкретные состояния были поставлены первыми, а записи ST_ANY продолжались с тех пор, как приоритет правил зависел от их положения в массиве. Первое найденное правило было использовано.

Кроме того, я помню, что у нас был массив индексов для первого правила для каждого состояния, чтобы ускорить поиск (все правила с одинаковым стартовым состоянием были сгруппированы).

Также имейте в виду, что это был чистый C. Возможно, это лучший способ сделать это с C++.

Answer 5

Несколько парней из AT & T, теперь в Google, написал одну из лучших библиотек FSM, доступных для общего использования. Проверьте здесь, это называется OpenFST.

Это быстро, эффективно, и они создали очень четкий набор операций, которые вы можете выполнять в FSM, чтобы делать такие вещи, как минимизировать их или определять их, чтобы сделать их еще более полезными для проблем реального мира.

Answer 6

Конечный автомат состоит из конечного числа дискретных состояний (я знаю педантичный, но все же), который обычно может быть представлен как целочисленные значения. В c или C++ использование перечисления очень распространено.

Машина реагирует на конечное количество входов, которые часто могут быть представлены другой целочисленной переменной. В более сложных случаях вы можете использовать структуру для представления состояния ввода.

Каждая комбинация внутреннего состояния и внешнего входа вызовет машину к:

1. , возможно, переход в другое состояние
2. возможно сгенерировать выходной сигнал

простой случай с может выглядеть это

enum state_val { 
    IDLE_STATE, 
    SOME_STATE, 
    ... 
    STOP_STATE 
} 
//...  
    state_val state = IDLE_STATE 
    while (state != STOP_STATE){ 
    int input = GetInput(); 
    switch (state) { 
    case IDLE_STATE: 
     switch (input) { 
     case 0: 
     case 3: // note the fall-though here to handle multiple states 
      write(input); // no change of state 
      break; 
     case 1: 
      state = SOME_STATE; 
      break 
     case 2: 
      // ... 
     }; 
     break; 
    case SOME_STATE: 
     switch (input) { 
     case 7: 
      // ... 
     }; 
     break; 
    //... 
    }; 
    }; 
    // handle final output, clean up, whatever 

хотя это трудно читать и вновь легко разделить на многочисленные функции что-то вроде:

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

с сложностями каждого государства, состоявшейся в его собственной функции.

Как m3rLinEz says, вы можете провести переходы в массиве для быстрой индексации. Вы также можете удерживать указатель функции в массиве, чтобы эффективно обрабатывать фазу действия. Это особенно полезно для автоматической генерации больших и сложных государственных машин.

Answer 7

Ответы здесь кажутся очень сложными (но точными, тем не менее.) Итак, вот мои мысли.

Во-первых, мне нравится dmckee (рабочее) определение FSM и как они применяются к программированию.

конечный автомат состоит из конечного числа дискретных состояний (я знаю, педантичным, но до сих пор), который может как правило, быть представлен в виде целых значений . В c или C++ с использованием перечисления очень распространено перечисление.

Машина реагирует на конечное число входов, которые часто могут быть , представленного с другим числом значной переменной. В более сложных случаях вы можете использовать структуру для , представляя состояние ввода.

Каждая комбинация внутреннего состояния и внешний вход заставит машину к:

1. возможно переход в другое состояние
2. возможно генерировать некоторый вывод

Итак, вы программа. Он имеет состояния, и их конечное число. («лампочка яркая» или «лампочка тусклая» или «лампочка выключена». 3 состояния конечны.) Ваша программа может быть только в одном состоянии за раз.

Итак, скажите, что вы хотите, чтобы ваша программа меняла состояния. Обычно вам нужно что-то произойти, чтобы вызвать изменение состояния. В этом примере, как насчет ввода пользовательского ввода для определения состояния - скажем, нажатия клавиши.

Возможно, вам понадобится такая логика. Когда пользователь нажимает клавишу:

1. Если лампа выключена, сделайте лампу «тусклой».
2. Если лампа «тускнеет», сделайте лампу «яркой».
3. Если лампа «яркая», сделайте лампу «выключено».

Очевидно, вместо того, чтобы «менять лампу», вы можете «менять цвет текста» или что бы то ни было, что вам нужно выполнить программе. Прежде чем начать, вы захотите определить свои состояния.

Так, глядя на код 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; 
    } 
} 

И, вуаля. Простая программа, которая изменяет состояние.

Этот код выполняет лишь небольшую часть инструкции switch - в зависимости от состояния . Затем это обновления, что состояние. Вот как работают FSM.

Теперь вот некоторые вещи, которые вы можете сделать:

1. Очевидно, что эта программа просто изменяет переменную currentState. Вы хотите, чтобы ваш код делал что-то более интересное при изменении состояния. Функция doCoolBulbStuff() может, я не знаю, на самом деле поставить изображение лампочки на экране. Или что-то.

2. Этот код ищет только нажатия клавиши. Но ваш FSM (и, следовательно, ваш оператор switch) может выбирать состояние, основанное на том, что вводил пользователь (например, «O» означает «перейти в выключенное состояние», а не просто идти к тому, что будет дальше в последовательности.)

Часть вашего вопроса требует структуры данных.

Один человек предложил использовать enum для отслеживания состояний. Это хорошая альтернатива #defines, которую я использовал в моем примере. Люди также предлагали массивы - и эти массивы отслеживают переходы между государствами. Это также тонкая структура для использования.

Учитывая вышеизложенное, вы можете использовать любую структуру (что-то древовидное, массив, что угодно), чтобы отслеживать отдельные состояния и определять, что делать в каждом состоянии (следовательно, некоторые из предложений использовать «указатели функций» - иметь карту состояний для указателя функции, который указывает, что делать в этом состоянии.)

Надеюсь, что это поможет!