有限状态机,也称为FSM(Finite State Machine)，其在任意时刻都处于有限状态集合中的某一状态。当其获得一个输入字符时，将从当前状态转换到另一个状态，或者仍然保持在当前状态。任何一个FSM都可以用状态转换图来描述，图中的节点表示FSM中的一个状态，有向加权边表示输入字符时状态的变化。如果图中不存在与当前状态与输入字符对应的有向边，则FSM将进入“消亡状态(Doom State)”，此后FSM将一直保持“消亡状态”。状态转换图中还有两个特殊状态：状态1称为“起始状态”，表示FSM的初始状态。状态6称为“结束状态”，表示成功识别了所输入的字符序列。

在启动一个FSM时，首先必须将FSM置于“起始状态”，然后输入一系列字符，最终，FSM会到达“结束状态”或者“消亡状态”。

说明：

在通常的FSM模型中，一般还存在一个“接受状态”，并且FSM可以从“接受状态”转换到另一个状态，只有在识别最后一个字符后，才会根据最终状态来决定是否接受所输入的字符串。此外，也可以将“其实状态”也作为接受状态，因此空的输入序列也是可以接受的。

FSM的实现

程序设计思路大致如下：

  • 使用状态转换图描述FSM
  • 状态转换图中的结点对应不同的状态对象
  • 每个状态对象通过一个输入字符转换到另一个状态上，或者保持原状态不变。

通过输入字符从一个状态切换到另一个状态的过程，我们称之为一个映射。在计算机程序设计中，我们可以有两种表示映射的方法：

  • 通过算法表示，即“可执行代码（Executable Code）”方式
  • 通过一张映射表，即“被动数据（Passive Data）”方式

如下详细介绍这两种实现方式：

  • 通过Executable Code实现映射的FSM：

这种方式主要是通过条件分支来处理不同的字符，如if或者switch语句块，如

 State* State1::Transition(char c)

 {

     switch(c)

     {

     case 'A':

         return &s2;

     case 'B':

         return &s3;

     case 'C':

         return &s4;

     case 'D':

         return &s5;

     case '\0':

         return NULL;

     default:

         return NULL;

     }

 }
  • 通过Passive Data实现映射的FSM：

在如上的switch分支中，其使用类型大致相同，因此，我们可以考虑将相似的信息保存到一张表中，这样就可以在程序中避免很多函数调用。在每个状态中都使用一张转换表来表示映射关系，转换表的索引使用输入字符来表示。此外，由于通过转换表就可以描述不同状态之间的变化，那么就没有必要将每种状态定义为一个类了，即不需要多余的继承和虚函数了，仅使用一个State即可。

 #include <limits.h>

 class State

 {

 public:

     State();

     State* transition[range];

 };

 对于任意一个状态state和输入字符c，后续状态都可以通过state.transition[c]来确定。

 类Fsm中的成员state包含6个状态，为了对应方便，我们将结束状态放在state[]中，每个状态都使用一个三元组 { 当前状态，输入字符，下一个状态 } 来表示：

 struct TransGraph   // use triple to describe map

 {

     int current_state;

     char input_char;

     int next_state;

 };

如此，使用了转换表代替了虚函数，简化了程序的设计。

 // fsm_with_passive_data.h

 #ifndef FSM_WITH_PASSIVE_DATA_H

 #define FSM_WITH_PASSIVE_DATA_H

 #include <string.h>

 #include <limits.h>     // CHAR_MAX

 const int range = CHAR_MAX + ;

 class State

 {

 public:

     State();

     State* transition[range];

 };

 struct TransGraph   // use triple to describe map

 {

     int current_state;

     char input_char;

     int next_state;

 };

 class Fsm

 {

 public:

     Fsm();

     void Reset();            // move to start state

     void Advance(char c);    // advance one transition

     int EndState();

     int DoomState();

 private:

     State* p_current;   // &s1, &s2, ..., &s6; NULL ==> doom

     State state[];     // 6 states, state[0] is end state

 };

 #endif // FSM_WITH_PASSIVE_DATA_H

 // fsm_with_passive_data.cc

 #include "fsm_with_passive_data.h"

 State::State()

 {

     for (int i = ; i < range; ++i)

         transition[i] = NULL;

 }

 Fsm::Fsm()

 {

     static TransGraph graph[] =

     {

         {, 'A', }, {, 'B', }, {, 'C', }, {, 'D', },

         {, 'E', }, {, 'I', },

         {, 'F', }, {, 'J', }, {, 'M', },

         {, 'G', }, {, 'K', },

         {, 'H', }, {, 'L', }, {, 'O', }, {, 'N', },

         {, , }

     };

     for (TransGraph* p_tg = graph; p_tg->current_state != ; ++p_tg)

         state[p_tg->current_state].transition[p_tg->input_char] = &state[p_tg->next_state];

     p_current = NULL;

 }

 void Fsm::Reset()

 {

     p_current = &state[];

 }

 void Fsm::Advance(char c)

 {

     if (p_current != NULL)

         p_current = p_current->transition[c];

 }

 int Fsm::EndState()

 {

     return p_current == &state[];

 }

 int Fsm::DoomState()

 {

     return p_current == NULL;

 }

 // test_with_passive_data.cc

 #include "fsm_with_passive_data.h"

 #include "stdio.h"  // printf, scanf

 #include "stdlib.h" // system

 void test_fsm()

 {

     char input_string[];

     printf("Enter input expression: ");

     scanf("%s", input_string);

     Fsm fsm;

     fsm.Reset();

     int index = ;

     fsm.Advance(input_string[index++]);

     while (!fsm.EndState() && !fsm.DoomState())

         fsm.Advance(input_string[index++]);

     if (fsm.EndState())

         printf("\nValid input expression");

     else

         printf("\nInvalid input expression");

 }

 int main()

 {

     test_fsm();

     system("pause");

 }

通用FSM的设计

如果类Fsm可以表示任意类型的FSM，那么就更符合程序设计的要求了。在构造函数中执行的具体配置应该被泛化为一种机制，我们通过这种机制来建立任意的FSM。在Fsm的构造函数中，应该将转换表作为一个参数传入，而非包含具体的转换表，如此，则不需要将转换表的大小硬编码到Fsm中了。因此，在构造函数中必须动态地创建这个存放转换表的内存空间，在析构函数中记着销毁这块内存。

 class Fsm

 {

 public:

     Fsm(TransGraph* p_tg);

     virtual ~Fsm();

     void Reset();

     void Advance(char c);

     int EndState();

     int DoomState();

 private:

     State* p_current;

     State* p_state;

 };

 Fsm::Fsm(TransGraph* p_tg)

 {

     int max_state = ;  // size for dynamically allocated graph

     for (TransGraph* p_temp = p_tg; p_temp->current_state != ; ++p_temp)

     {

         if (p_temp->current_state > max_state)

             max_state = p_temp->current_state;

         if (p_temp->next_state > max_state)

             max_state = p_temp->next_state;

     }

     p_state = new State[max_state + ];

     for (TransGraph* p_temp = p_tg; p_temp->current_state != ; ++p_temp)

         p_state[p_temp->current_state].transition[p_temp->input_char] = &p_state[p_temp->next_state];

     p_current = NULL;

 }

 Fsm::~Fsm()

 {

     delete []p_state;

 }
 // fsm_with_generalization.h

 #ifndef FSM_WITH_GENERALIZATION_H

 #define FSM_WITH_GENERALIZATION_H

 #include <string.h>

 #include <limits.h>     // CHAR_MAX

 const int range = CHAR_MAX + ;

 class State

 {

 public:

     State();

     State* transition[range];

 };

 struct TransGraph

 {

     int current_state;

     char input_char;

     int next_state;

 };

 class Fsm

 {

 public:

     Fsm(TransGraph* p_tg);

     virtual ~Fsm();

     void Reset();

     void Advance(char c);

     int EndState();

     int DoomState();

 private:

     State* p_current;

     State* p_state;

 };

 #endif // FSM_WITH_GENERALIZATION_H

 // fsm_with_generalization.cc

 #include "fsm_with_generalization.h"

 State::State()

 {

     for (int i = ; i < range; ++i)

         transition[i] = NULL;

 }

 Fsm::Fsm(TransGraph* p_tg)

 {

     int max_state = ;  // size for dynamically allocated graph

     for (TransGraph* p_temp = p_tg; p_temp->current_state != ; ++p_temp)

     {

         if (p_temp->current_state > max_state)

             max_state = p_temp->current_state;

         if (p_temp->next_state > max_state)

             max_state = p_temp->next_state;

     }

     p_state = new State[max_state + ];

     for (TransGraph* p_temp = p_tg; p_temp->current_state != ; ++p_temp)

         p_state[p_temp->current_state].transition[p_temp->input_char] = &p_state[p_temp->next_state];

     p_current = NULL;

 }

 Fsm::~Fsm()

 {

     delete []p_state;

 }

 void Fsm::Reset()

 {

     p_current = &p_state[];

 }

 void Fsm::Advance(char c)

 {

     if (p_current != NULL)

         p_current = p_current->transition[c];

 }

 int Fsm::EndState()

 {

     return p_current == &p_state[];

 }

 int Fsm::DoomState()

 {

     return p_current == NULL;

 }

 // test_with_generalization.cc

 #include "fsm_with_generalization.h"

 #include "stdio.h"  // printf, scanf

 #include "stdlib.h" // system

 void test_fsm()

 {

     char input_string[];

     printf("Enter input expression: ");

     scanf("%s", input_string);

     TransGraph graph[] =

     {

         {, 'A', }, {, 'B', }, {, 'C', }, {, 'D', },

         {, 'E', }, {, 'I', },

         {, 'F', }, {, 'J', }, {, 'M', },

         {, 'G', }, {, 'K', },

         {, 'H', }, {, 'L', }, {, 'O', }, {, 'N', },

         {, , }

     };

     Fsm fsm(graph);

     fsm.Reset();

     int index = ;

     fsm.Advance(input_string[index++]);

     while (!fsm.EndState() && !fsm.DoomState())

         fsm.Advance(input_string[index++]);

     if (fsm.EndState())

         printf("\nValid input expression");

     else

         printf("\nInvalid input expression");

 }

 int main()

 {

     test_fsm();

     system("pause");

 }

当然也可以将上述程序中的转换表不放在主程序中，而是由一个派生自Fsm的子类SpecificFsm提供，在SpecificFsm中设置具体的转换表，然后通过SpecificFsm的初始化列表传到基类Fsm中，这样在主程序中就可以使用SpecificFsm来进行操作了。

原文地址：http://www.cnblogs.com/benxintuzi/p/4931258.html

最新文章

  1. Javascript优化后的加减乘除（解决js浮点数计算bug）
  2. 实现TCP、UDP相互通信及应用
  3. [No000060]冷读热读：读书九问
  4. 《热血传奇2》wix、wil文件解析Java实现
  5. Swift使用FMDB操作SQLite
  6. -- Warning: Skipping the data of table mysql.event. Specify the --events option explicitly.
  7. uC/OS-II 移植笔记
  8. Less 官方文档学习笔记
  9. 关于group by
  10. Java面向对象之封装 入门实例（一）
  11. MySQL自定义函数与存储过程
  12. 分布式协调服务Zookeeper集群之ACL篇
  13. 从.Net到Java学习第五篇——Spring Boot &amp;&amp;Profile &amp;&amp;Swagger2
  14. AES加密的S盒和逆S盒的推导代码备份(C实现)
  15. python之路--触发器, 储存过程, 事务
  16. VMware与Centos系统安装 和重置root密码
  17. ５.6 C++重载下标操作符
  18. Warning the user/local/mysql/data directory is not owned by the mysql user
  19. App登录状态维持
  20. XMemcached使用经历

热门文章

  1. lftp查看文件时间与登录服务查看文件时间相差8小时
  2. VS2010中水晶报表插件下载安装方法
  3. singer页左侧滚动的时候右侧跟随高亮显示
  4. spring容器的配置和springmvc的配置
  5. 第2章 初学 emWin 的准备工作及其快速上手
  6. JAVA-MyEclipse第一个实例
  7. pionter指针小结
  8. SecureCRT连接AWS EC2云主机密码登录
  9. HTML文档的经常使用标记
  10. Hibernate- hibernate二级缓存