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

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

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

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

Можно в основном использовать "если" условное выражение и переменная для хранения текущего состояния 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){
        ...
    }
}

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

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

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

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

/* 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++.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Учитывая вышеизложенное, вы можете использовать любую структуру (что-то вроде дерева, массив, что угодно), чтобы отслеживать отдельные состояния и определять, что делать в каждом состояние (отсюда и некоторые предложения по использованию "

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

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