有限状态机(FSM)是一个根据输入改变状态的机器或程序。用图表示 FSM 相当简明， 下图中的矩形(或圆形)称为节点，节点之间带箭头的线段称为边(或弧)。
 

 
上图给出了一个简单的例子。每个节点代表一个程序状态，每个边代表从一个状态到另一个状态的转换。一个节点被指定为初始状态，在图中用一个输入箭头指出。其余的状态可以用数字或字母来标示。一个或多个状态可以指定为终止状态，用粗框矩形表示。终止状态表示程序无出错的结束状态。
 
FSM 是一种被称为有向图的更一般结构的特例。有向图就是一组节点，它们用具有特定方向的边进行连接。
 
验证输入字符串
 
读取输入流的程序往往要通过执行一定量的错误检查来验证它们的输入。比如，编程语言编译器可以用 FSM 来扫描程序，将文字和符号转换为记号(通常是指关键字、算法运算符和标识符)。
 
用 FSM 来验证输入字符串时，常常是按字符进行读取。每一个字符都用图中的一条边(转换)来表示。FSM 有两种方法检测非法输入序列：
 
下一个输入字符没有对应到当前状态的任何一个转换。
 
输入已经终止，但是当前状态是非终止状态。
 
字符串示例现在根据下面两条原则来验证一个输入字符串：
 
该字符串必须以字母“x”开始，以字母“z”结束。
 
第一个和最后一个字符之间可以有零个或多个字母，但其范围必须是 {a,....,y}。
 
下图的 FSM 显示了上述语法。每一个转换都是由特定类型的输入来标识。比如，仅当从输入流中读取字母 x 时，才能完成状态 A 到状态 B 的转换。输入任何非“z”的字母，都会使得状态 B 转换为其自身。而仅当从输入流中读取字母 z 时，才会发生状态 B 到状态 C 的转换。
 

 
如果输入流已经结束，而程序只出现了状态 A 和状态 B，那么就生成出错条件，因为只有状态 C 才能标记终止状态。下述输入字符串能被该 FSM 认可：
 
xaabcdefgz
 
xz
 
xyyqqrrstuvz
 
验证有符号整数
 
下图表示的是 FSM 解析一个有符号整数。输入包括一个可选的前置符号，其后跟一串数字。图中没有对数字个数进行限制。
 

 
有限状态机很容易转换为汇编代码。图中的每个状态(A、B、C…)代表了一段有标号的程序。每个标号执行的操作如下：
 
1) 调用输入程序读入下一个输入字符。
 
2)    如果是终止状态，则检查用户是否按下 Enter 键来结束输入。
 
3)    一个或多个比较指令检查从状态发岀的所有可能的转换。每个比较指令后面跟一个条件跳转指令。
 
比如，在状态 A，如下代码读取下一个输入字符并检查到状态 B 的可能的转换：
 
StateA:
 
Cal1 Getnext ;读取下一个字符，并送入 AL
 
cmp al, '+' ;前置+ ?
 
je StateB ;到状态 b
 
cmp al, '-' ;前置 - ?
 
je StateB ;到状态 B
 
call IsDigit ;如果 AL 包含数字，则 ZF = 1
 
jz StateC ;到状态 C
 
call DisplayErrorMsg ;发现非法输入
 
jmp Quit
 
下面来更详细地检查这段代码。首先，代码调用 Getnext，从控制台输入读取下一个字符，送入 AL 寄存器。接着检查前置 + 或 -，先将 AL 的值与符号“+”进行比较，如果匹配，就发生到标号 StateB 的跳转：
 
StateA:
 
call Getnext ;读取下一个字符，并送入 al
 
cmp al, ' + ' ;前置 + ?
 
je StateB ;到状态 B
 
现在，再次查看上图，发现只有输入 + 或 - 时，才发生状态 A 到状态 B 的转换。所以，代码还需检查减号：
 
cmp al, '-' ;前置 - ？
 
je StateB ;到状态 B
 
如果无法发生到状态 B 的转换，就可以检查 AL 寄存器中是否为数字，这可以导致到状态 C 的转换。调用 IsDigit 子程序，当 AL 包含数字时，零标志位置 1：
 
call IsDigit ;如果AL包含数字，贝U ZF=1
 
jz StateC ;到状态 C
 
最后，状态 A 没有其他可能的转换。如果发现 AL 中的字符既不是前置符号，又不是数字，程序就会调用 DisplayErrorMsg (在控制台上显示一条错误消息)子程序，并跳转到标号 Quit 处：
 
call DisplayErrorMsg ;发现非法输入
 
jmp Quit
 
标号 Quit 标识程序的出口，位于主程序的结尾：
 
Quit:
 
call Crlf
 
exit
 
main ENDP
 
完整的有限状态机程序
 
如下程序实现上图所示的有符号整数 FSM：
 
; 有限状态机 (Finite.asm)
 
INCLUDE Irvine32.inc
 
ENTER_KEY = 13
 
.data
 
InvalidInputMsg BYTE "Invalid input",13,10,0
 
.code
 
main PROC
 
call Clrscr
 
StateA:
 
call Getnext ; 读取下一个字符，并送入AL
 
cmp al,'+' ; 前置+ ?
 
je StateB ; 到状态 B
 
cmp al,'-' ; 前置 - ?
 
je StateB ; 到状态 B
 
call IsDigit ; 如果 AL 包含数字 ，则 ZF = 1
 
jz StateC ; 到状态 C
 
call DisplayErrorMsg ; 发现非法输入
 
jmp Quit
 
StateB:
 
call Getnext ; 读取下一个字符，并送入AL
 
call IsDigit ; 如果AL包含数字，则 ZF = 1
 
jz StateC
 
call DisplayErrorMsg ; 发现非法输入
 
jmp Quit
 
StateC:
 
call Getnext ; 读取下一个字符，并送入AL
 
call IsDigit ; 如果AL包含数字，则 ZF = 1
 
jz StateC
 
cmp al,ENTER_KEY ; 按下Enter键?
 
je Quit ; 是：Quit
 
call DisplayErrorMsg ; 否: 发现非法输入
 
jmp Quit
 
Quit:
 
call Crlf
 
exit
 
main ENDP
 
;-----------------------------------------------
 
Getnext PROC
 
;
 
; 从标准输入读取一个字符
 
; 接收: 无
 
; 返回: 字符保存在AL中
 
;-----------------------------------------------
 
call ReadChar ; 从键盘输入
 
call WriteChar ; 显示在屏幕上
 
ret
 
Getnext ENDP
 
;-----------------------------------------------
 
DisplayErrorMsg PROC
 
;
 
; 显示一个错误消息以表示
 
; 输入流中包含非法输入
 
; 接收: 无.
 
; 返回: 无
 
;-----------------------------------------------
 
push edx
 
mov edx,OFFSET InvalidInputMsg
 
call WriteString
 
pop edx
 
ret
 
DisplayErrorMsg ENDP
 
END main
 
IsDigit子程序
 
有限状态机示例程序调用 IsDigit 子程序，该子程序属于本教程的链接库。现在来看看 IsDigit 的源程序，程序把 AL 寄存器作为输入，其返回值设置零标志位：
 
;----------------------------------------------------
 
IsDigit PROC
 
;
 
;确定 AL 中的字符是否为有效的十进制数字。
 
;接收：AL= 字符
 
;返回：若 AL 为有效的十进制字符，ZF=1;否则，ZF=0
 
;---------------------------------------------------
 
cmp al,'0'
 
jb ID1 ;跳转发生，ZF=0
 
cmp al, '9'
 
ja ID1 ;跳转发生，ZF = 0
 
test ax, 0 ;设置 ZF=1
 
ID1: ret
 
IsDigit ENDP
 
在查看 IsDigit 的代码之前，先回顾十进制数字的十六进制 ASCII 码，如下表所示。由于这些值是连续的，因此，只需要检查第一个和最后一个值：
 
字符
 
'0'
 
'1'
 
'2'
 
'3'
 
'4'
 
'5'
 
'6'
 
'7'
 
'8'
 
'9'
 
ASCII 码(十六进制)
 
30
 
31
 
32
 
33
 
34
 
35
 
36
 
37
 
38
 
39
 
IsDigit 子程序中，开始的两条指令将 AL 寄存器中字符的值与数字 0 的 ASCII 码进行比较。如果字符的 ASCII 码小于 0 的 ASCII 码，程序跳转到标号 ID1：
 
cmp al, '0'
 
jb ID1 ;跳转发生，ZF=0
 
但是有人可能会问了，如果 JB 将控制传递给标号 ID1，那么，怎么知道零标志位的状态呢？答案就在 CMP 指令的执行方式里——它执行一个隐含的减法操作，从 AL 寄存器的字符中减去 0 的 ASCII 码(30h)。如果 AL 中的值较小，那么进位标志位置 1，零标志位清除(你可能想用调试器来单步执行这段代码来验证这个事实)。JB 指令的目的是，当 CF=1 且 ZF=0 时，将控制传递给一个标号。
 
接下来，IsDigit 子程序代码把 AL 与数字 9 的 ASCII 码进行比较。如果 AL 的值较大，代码跳转到同一个标号：
 
cmp al, '9'
 
ja ID1 ;跳转发生，ZF=0
 
如果 AL 中字符的 ASCII 码大于数字 9 的 ASCII 码(39h)，清除进位标志位和零标志位。这也正好是使得 JA 指令将控制传递到目的标号的标志位组合。
 
如果没有跳转发生(JA 或 JE)，又假设 AL 中的字符确实是一个数字，则插入一条指令确保将零标志位置 1。将 0 与任何数值进行 test 操作，就意味着执行一次隐含的与全 0 的 AND 运算。其结果必然为 0：
 
test ax, 0          ; 置 ZF=1
 
前面 IsDigit 中的 JA 和 JB 指令跳转到了 TEST 指令后面的标号。所以，如果发生跳转，零标志位将清零。下面再次给出完整的过程：
 
Isdigit PROC
 
cmp al,'0'
 
jb ID1 ;若跳转发生，则 ZF=0
 
cmp al,'9'
 
ja ID1 ;若跳转发生，则 ZF=0
 
test ax,0 ;置 zf=1
 
ID1: ret
 
Isdigit ENDP
 
在实时或高性能应用中，程序员常常利用硬件特性的优势，来对其代码进行充分优化。IsDigit 过程就是这种方法的例子，它利用 JB、JA 和 TEST 对标志的设置，实际上返回的是一个布尔结果。

 
最近在项目中，涉及到对行为和状态进行建模的需求，尝试用有限状态机(Finite-state machine, FSM)来实现。
 
1. 概念介绍
 
1.1 运行机制
 
基于对有限状态机的粗浅理解，大体的运行机制为：
 
系统所处的状态是明确并且有限的，必定属于状态全集中的某一种；
 
系统接受输入，根据判定条件，决定是维持当前状态，还是切换到某一个新的状态；
 
在维持或切换的过程中，执行一些预设的操作。
 
可以认为有限状态机是一个离散系统，每接受一次输入，进行一次判断和切换。
 
1.2 所含要素
 
一个有限状态机包含如下几个要素：
 
状态：系统所处的状态，在运行过程中又可以分为当前状态和下一阶段状态；
 
事件：也可以理解为每一次运行的输入；
 
条件：根据输入事件执行的判定条件，条件是基于状态的，当前所处的每一种状态，都可以有自己对应的一套判定条件，来决定下一步进入哪一种状态；
 
动作：确定切换路径后，执行的附加操作。
 
以一个共3种状态的FSM为例，共有3套判定条件，根据当前所处的状态来确定使用哪一种判定条件，共有3*3=9种动作，决定每一种状态切换过程中需要执行的动作。
 
1.3 分析方法
 
通常可以用一个表格来对所处理的FSM进行分析，防止情况的遗漏。
 

 
在表格中分析清楚每一种状态切换的判定条件和执行动作，再用代码实现，可以最大程度地减轻思考的难度，减少错误的概率。
 
2. 代码实现
 
以OOP的方式，做了一个基础的Python实现。
 
FSM基类：
 
class StateMachine:
 
def __init__(self, cfg, states, events_handler, actions_handler):
 
# config information for an instance
 
self.cfg = cfg
 
# define the states and the initial state
 
self.states = [s.lower() for s in states]
 
self.state = self.states[0]
 
# process the inputs according to current state
 
self.events = dict()
 
# actions according to current transfer
 
self.actions = {state: dict() for state in self.states}
 
# cached data for temporary use
 
self.records = dict()
 
# add events and actions
 
for i, state in enumerate(self.states):
 
self._add_event(state, events_handler[i])
 
for j, n_state in enumerate(self.states):
 
self._add_action(state, n_state, actions_handler[i][j])
 
def _add_event(self, state, handler):
 
self.events[state] = handler
 
def _add_action(self, cur_state, next_state, handler):
 
self.actions[cur_state][next_state] = handler
 
def run(self, inputs):
 
# decide the state-transfer according to the inputs
 
new_state, outputs = self.events[self.state](inputs, self.states, self.records, self.cfg)
 
# do the actions related with the transfer
 
self.actions[self.state][new_state](outputs, self.records, self.cfg)
 
# do the state transfer
 
self.state = new_state
 
return new_state
 
def reset(self):
 
self.state = self.states[0]
 
self.records = dict()
 
return
 
# handlers for events and actions, event_X and action_XX are all specific functions
 
events_handlers = [event_A, event_B]
 
actions_handlers = [[action_AA, action_AB],
 
[action_BA, action_BB]]
 
# define an instance of StateMachine
 
state_machine = StateMachine(cfg, states, events_handlers, actions_handlers)
 
如果对于状态机有具体的要求，可以继承这个基类进行派生。
 
比如，有对状态机分层嵌套的需求。
 
class StateGeneral(StateMachine):
 
def __init__(self, cfg, states):
 
super(StateGeneral, self).__init__(cfg, states, events_handler, actions_handler)
 
self.sub_state_machines = dict()
 
def add_sub_fsm(self, name, fsm):
 
self.sub_state_machines[name] = fsm
 
def run(self, inputs):
 
new_state, outputs = self.events[self.state](inputs, self.states, self.records, self.cfg)
 
# operate the sub_state_machines in actions
 
self.actions[self.state][new_state](outputs, self.records, self.cfg, \
 
self.sub_state_machines)
 
self.state = new_state
 
return new_state
 
def reset(self):
 
self.state = self.states[0]
 
self.records = dict()
 
for _, sub_fsm in self.sub_state_machines.items():
 
sub_fsm.reset()
 
return

% Test the sf_lamp_logic chart object
 
% 1. Create the chart object and initialize the value of delay to 1.
 
L = sf_lamp_logic('delay',1);
 pause(2)
 
% 2. Turn lamp on.
 
ON(L);
 pause(2)
 
% 3. Switch to blinking mode.
 
BLINKING(L);
 pause(2)
 
% 4. Set value of delay to 0.5.
 
L.delay = 0.5;
 pause(2)
 
% 5. Switch to solid mode.
 
SOLID(L);
 pause(2)
 
% 6. Turn lamp off.
 
OFF(L);
 pause(2)
 
% 7. Delete chart object.
 
delete(L);
  
 
 
 

 
在matlab中画向量图用到的函数是：quiver
 
函数 通过help 命令可以得到
 
quiver函数的常用方法，在本文中，只介绍关于状态方程的向量图的用法：
 
(1)如给定的形式如：x'=1-x^2-y^2;y'=2xy;
 
matlab 程序如下：
 
%对微分方程组：x'=1-x.^2-y.^2,y'=2xy;绘制向量场
 
x0=-3:.5:3;%选定范围
 
y0=-3:.5:3;
 
[x y]=meshgrid(x0,y0);%设定绘制点
 
d=sqrt((1-x.^2-y.^2).^2+(2*x.*y).^2);
 
u=(1-x.^2-y.^2)./d;
 
v=(2*x.*y)./d;%u v是相应点(x,y)的指示方向
 
hold on
 
quiver(x,y,u,v,0.1,'b');%绘画向量场
 
(2)如给定形式是：x'=1-x^2;
 
这时只有一个变量x,我们就添加t作为第二个变量，得到的方程：t'=1;x'=1-x^2;
 
matlab程序如下：
 
clear
 
c=0.3;
 
x0=-5:.5:5;
 
y0=-5:.5:5;
 
[x,y]=meshgrid(x0,y0);
 
d=sqrt(1^2+(1-y.^2).^2);
 
u=c./d;
 
v=c*(1-y.^2)./d;
 
hold on
 
quiver(x,y,u,v);