Дизайн структуры данных FSM

Question

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

Спасибо, syuga2012

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Возможно, вы захотите такую ​​логику. Когда пользователь нажимает клавишу:

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

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

Итак, посмотрим на какой-то псевдоиш-код 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 - в зависимости от текущего состояния . Затем он обновляет это состояние. Вот как работают автоматы.

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

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

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

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

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

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

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

Answer 3

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

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

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

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

Простой случай в c может выглядеть следующим образом

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 , вы можете хранить переходы в массиве для быстрой индексации. Вы также можете держать указатель на функцию в массиве для эффективной обработки фазы действия. Это особенно полезно для автоматической генерации больших и сложных конечных автоматов.

Answer 4

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

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

Answer 5

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

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

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 6

См. Википедия для формального определения. Вам необходимо выбрать набор состояний S , ваш входной алфавит и сигма; и ваша функция перехода & delta ;. Самое простое представление: S будет набором целых чисел 0, 1, 2, ..., N -1, где N - число состояния и для & Sigma; быть набором целых чисел 0, 1, 2, ..., M -1, где M - количество входов, а затем & delta; это просто большая N по M матрица. Наконец, вы можете сохранить набор принимающих состояний, сохранив массив из N битов, где i th бит равен 1, если i th состояние принимающее состояние или 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 7

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

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

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