FSM数据结构设计

Question

我想编写一个 FSM，它从空闲状态开始，并根据某些事件从一种状态移动到另一种状态。 我不熟悉 FSM 的编码，谷歌没有帮助。 如果有人可以发布可用于相同目的的 C 数据结构，我将不胜感激。

谢谢， 苏加2012

Answer 1

有限状态机由有限数量的离散状态组成（我知道这很迂腐，但仍然如此），它们通常可以表示为整数值。 在 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 2

这里的答案看起来非常复杂（但仍然准确）。所以这是我的想法。

首先，我喜欢 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 语句的一小部分 - 取决于当前状态。 然后它更新该状态。 这就是 FSM 的工作原理。

现在您可以执行以下操作：

1. 显然，该程序只是更改了currentState 变量。 您会希望您的代码在状态更改时执行更有趣的操作。 我不知道，doCoolBulbStuff() 函数实际上可能会将灯泡的图片显示在屏幕上。 或者其他什么。

2. 此代码仅查找按键。 但是您的 FSM（以及您的 switch 语句）可以根据用户输入的内容选择状态（例如，“O”表示“转到关闭”，而不是仅转到序列中的下一个。）

您提出的问题的一部分一个数据结构。

有人建议使用enum来跟踪状态。 这是我在示例中使用的 #defines 的一个很好的替代方案。 人们也一直在建议使用数组——这些数组会跟踪状态之间的转换。 这也是一个很好用的结构。

鉴于上述情况，您可以使用任何类型的结构（类似树的结构、数组等）来跟踪各个状态并定义在每个状态下执行的操作（因此一些建议使用“函数指针” “ - 有一个到函数指针的状态映射，指示在该状态下要做什么。）

希望有帮助！

Answer 3

有关正式定义，请参阅维基百科。 您需要决定您的状态集 S、您的输入字母 Σ 和您的转换函数 δ。 最简单的表示是让 S 为整数 0, 1, 2, ..., N-1 的集合，其中 N 是状态数，对于 Σ 来说，是整数 0, 1, 2, ..., M-1 的集合，其中 M 是输入的数量，并且那么 δ 只是一个大的 N × M 矩阵。 最后，您可以通过存储 N 位数组来存储接受状态集，其中，如果第 i 位为 1，则第 i 位为 1。 state 是接受状态，如果不是接受状态则为 0。

例如，维基百科文章图 3 中的 FSM 如下：

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

您基本上可以使用“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 5

来自 AT&T（现在在 Google）的几个人编写了可供通用使用的最好的 FSM 库之一。 在这里查看一下，它的名字是 OpenFST。

它快速、高效，并且他们创建了一组非常清晰的操作，您可以在 FSM 上执行这些操作，以执行诸如最小化它们或确定它们之类的操作，从而使它们对现实世界的问题更加有用。

Answer 6

如果 FSM 指的是有限状态机，
如果您喜欢简单，请使用枚举来命名您的状态
并在它们之间切换。

否则使用函子。 你可以看看
stl 或 boost 文档中的奇特定义。

它们或多或少是物体，具有
方法，例如调用 run()，执行
在那种状态下应该做的一切，
每个州都有自己的优势
范围。

Answer 7

我们过去为电信公司实现了有限状态机，并且始终使用结构数组，预先填充如下：

/* 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++ 来实现。