有限状态机的描述

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

在描述有限状态机时，状态、事件、转换和动作是经常会碰到的几个基本概念。

状态（State）：指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。

事件（Event）：指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。

转换（Transition）：指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。

动作（Action）：指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。

下面这个图是判断一个单词是否匹配nice的状态机图。
1、2、3、4、5、6、7分别是状态；剪头上的输入字母分别是事件；转换是从一个状态转换到一个状态，比如状态1输入n后就进入状态2.有了状态机。画出了状态机图，我们可以直观地看到每一个状态以及状态在事件产生时转化关系。

为什么要设计状态机？有了状态机，我们能记住自己目前所处的状态，这一点尤其重要，当你在每时每刻都可以明确目前所处的状态时，就可以做出相应的决策。并且在进入不同的状态时刻，可以做不同的操作。另外一点是可以把握整体的状态跟状态之间的转换，把非常复杂的关系简单化，并很方便地设计出相应的代码。

下面有几个例子，借助自定义的状态，可以使编程思路更加清晰。如果不用状态机，那么写起代码来会比较复杂或者可能会漏掉一些情况。

例子一：统计一个句子中的单词个数。

这个状态机有两个状态（state)
1、OUT，表示当前字符不在单词中，当前字符是空白字符(空格、制表符)
2、IN表示当前字符在单词中，当前字符非空白字符
显然字符只能处于上述两种状态之一。

有了这2个状态，我们接下来考虑状态的事件以及状态在事件产生时的转换 (Event&Transition;)
1、当前状态为OUT：若当前字符是空白字符，则维护当前状态仍为OUT；否则改变状态为IN。
2、当前状态为IN：若遇到的当前字符非空白字符，则维护当前状态为IN；否则改变状态为OUT。

处于不同的状态，根据题意可以给予相对应的动作(Action)
当前状态为OUT，若当前字符非空白字符，则改变状态为IN，说明一个单词开始了。此时单词个数自增。
初始状态为OUT，当处理完整个句子的时候，最后得出单词的总个数。从下面的代码可以看出来，当状态都正确描述后，关键语句只有一句count++就可以算出单词总个数

状态机如下：

代码如下：

#include 
#define OUT 0 /* outside a word */
#define IN 1  /* inside a word  */

int main(void)
{
    char c, state;
    int count = 0; //单词的个数
    state = OUT;
    while ( scanf("%c", &c;) != EOF && c != '\n' ) {
        if (state == OUT) {
            if (c == ' ' || c == '\t')
                state = OUT;
            else {
                state = IN;
                count++; //action
            }
        } else {
            if (c != ' ' && c != '\t') {
                state = IN;
            } else {
                state = OUT;
            }
        }
    }
     printf("单词个数：%d\n",count);
     return 0;
}

例子二：编写一个程序，删除C语言程序中所有的注释语句。在C语言中，注释不允许嵌套。

ps：为了更简单地描述状态机，我们在此不考虑单引号以及双引号里面的内容是注释，或者单行注释//中用\进行折行注释的情况

设计状态机如下：

00）设正常状态为0，并且初始为正常状态

每遍历一个字符，就依次检查下列条件，若成立或全部检查完毕，则回到这里检查下一个字符

01）状态0中遇到/，说明可能会遇到注释，则进入状态1　　　　　　　　　　例子： int a = b; /

02）状态1中遇到/，说明进入单行注释部分，则进入状态2　　　　　　　　　例子： int a = b; //

03）状态1中遇到*，说明进入多行注释部分，则进入状态3　　　　　　　　　例子： int a= b; /*

04）状态1中没有遇到*或/，说明/是路径符号或除号，则恢复状态0　　　　 例子： md5.h> or 83

05）状态2中遇到回车符\n，说明单行注释结束，则恢复状态0 　　　　　例子： int a = b; //hehe

06）状态2中不是遇到回车符\n，说明单行注释还在继续，则维持状态2 　例子： int a = b; //hehe

07）状态3中遇到*，说明多行注释可能要结束，则进入状态4　　　　　　　　例子： int a = b; /*heh*

08）状态3中不是遇到*，说明多行注释还在继续，则维持状态3　　　　　　　例子： int a = b; /*hehe

09）状态4中遇到/，说明多行注释要结束，则恢复状态0　　　　　　　　　　例子： int a = b; /*hehe*/

10）状态4中不是遇到/，说明多行注释只是遇到*，还要继续，则恢复状态3 　 例子： int a = b; /*hehe*h

上面的状态机涉及到了[0, 4]一共5种状态，对应的状态机如下：

有了这些状态表示，编写代码就很容易了——

/*
* 删除c语言中的单行跟多行注释，注意其中的action
*
*/

#include 
int main(void)
{
    char c, state;
    state = 0;
    while ((c = getchar()) != EOF)
     {
          if (state == 0)         
          {
               if (c == '/') // 例子： int a = b; /
               {
                    state = 1;
               }
               else
               {
                    putchar(c); //action
               }
          }
          else if (state == 1)
          {
               if (c == '/')  //例子： int a = b; //
               {
                    state = 2;

               }
               else if (c == '*')  //例子： int a= b; /*
               {
                    state = 3;
               }
               else  //例子： md5.h> or 83
               {
                    state = 0;
                    putchar('/'); //action
                    putchar(c); //action
               }
          }
          else if (state == 2)    
          {
               if (c == '\n')  //例子： int a = b; //hehe
               {
                    state = 0;
                    putchar(c); //action
               }
               //例子： int a = b; //hehe
          }
          else if (state == 3)    
          {
               if (c == '*')  //例子： int a = b; /*heh*
               {
                    state = 4;
               }
               //例子： int a = b; /*hehe
          }
          else if (state == 4)
          {
               if (c == '/')  //例子： int a = b; /*hehe*/
               {
                    state = 0;
               }
               else  //例子： int a = b; /*hehe*h
               {
                    state = 3;
               }
          }
          else
          {
               printf("state error!");
          }

     }
     return 0;
}

若我们生成可执行文件为DeleteComment.exe
用Test.c作为输入的测试用例，Test.c的内容为

#include 
#include md5.h>
int main(void)
{
     *hehe
       hehe
       */
     /*hehe*/
     int a, int b; /* hehe */
     //hehe
     a = 4/2; //hehe
    return 0;
}

把Test.c放到DeleteComment.exe同目录下，执行DeleteComment.exe < Test.c > TestAfterDeleteComment.c
则在同目录下会生成去掉注释的文件 TestAfterDeleteComment.c，内容为：

#include 
#include md5.h>
int main(void)
{

     int a, int b; 

     a = 42;
    return 0;
}

源代码：
https://github.com/helloitworks/algorithm/tree/master/fsm

例子三：分析一个url

url的一般格式是：protocol :// hostname[:port] / path[?query][#fragment]
要写代码分析出这个url的每一个组成部分出来，如果不用状态机，很有挑战性。
主要挑战性如下：
1、protocaol可以有多种协议，比如http ftp thunder emule bt等，这种协议是可以自定义的，所以并无法穷举。有些url有protocol，有些没有
2、可以有port，也可以没有port
3、path可以是目录名，也可以是文件名，也可以是多层目录加文件
4、可以有query，也可以没有query
5、可以有fragment,也可以没有fragment

如果使用状态机：
只要描定义出所有状态，明白状态之间的转换，然后执行相应的动作，相信分析一个url并不难，在此不赘述。

例子四：实现编译器的词法分析器

编辑器中的词法分析器，也是通过状态机来实现的。

还有更多更多的例子，比如正则表达式引擎，xml解析器，json解析器，css解析器等，都可以使用状态机进行解析。