6

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

谢谢， syuga2012

4

7 回答 7

5

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

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

于 2009-04-07T14:53:50.613 回答
2

有限状态机由有限数量的离散状态组成（我知道很迂腐，但仍然如此），通常可以表示为整数值。在 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 所说，您可以将转换保存在数组中以进行快速索引。您还可以将函数指针保存在数组中以有效地处理动作阶段。这对于自动生成大型复杂状态机特别有用。

于 2009-06-08T00:50:17.347 回答
2

这里的答案似乎真的很复杂（但仍然准确）。所以这是我的想法。

首先，我喜欢 dmckee 对 FSM 的（操作）定义以及它们如何应用于编程。

有限状态机由有限数量的离散状态组成（我知道很迂腐，但仍然如此），通常可以表示为整数值。在 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我在示例中使用的一个很好的替代方法。人们也一直在建议使用数组——这些数组跟踪状态之间的转换。这也是一个很好的结构。

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

希望有帮助！

于 2009-06-08T01:25:50.317 回答
1

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

例如，这里是 Wikipedia 文章图 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
}
于 2009-04-07T14:42:02.857 回答
1

您基本上可以使用“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){
        ...
    }
}
于 2009-04-07T14:42:33.137 回答
1

AT&T 的几个人，现在在谷歌，写了一个最好的可用于一般用途的 FSM 库。在这里查看它，它被称为OpenFST。

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

于 2009-06-06T20:26:01.240 回答
0

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

否则使用函子。您可以在 stl 或 boost 文档中查看花哨的定义。

它们或多或少是对象，有一个名为 run() 的方法，它执行在该状态下应该完成的所有事情，其优点是每个状态都有自己的范围。

于 2009-04-07T14:47:26.367 回答