下载掌阅APP，畅读海量书库
立即打开
自动售货机是日常所见的智能产品，依据售货机上的产品价格进行自动售货。自动售货机除了拥有接收付款功能外，还有自动出货功能。对于自动售货机，使用有限状态机进行建模明显是不够的，需要改造有限状态机使之能对出货功能进行建模。
在有限状态机基础上，增加输出集和输出函数，形成输入输出有限状态机，也称输入输出（Input Output）自动机。输入输出自动机应用于与环境交互或者自适应智能系统的建模。根据输出函数的不同又将这种自动机分为两类：Moore型自动机和Mealy型自动机。
定义2.2（输入输出有限状态机） 输入输出有限状态机形式化地定义为一个5元组( S , I , O , f , h , s 1 )，其中 S 是有限状态集{ s 1 , s 2 ,…, s n }， I 是输入集{ i 1 , i 2 ,…, i m }， O 是输出集{ o 1 , o 2 ,…, o k }， f 是状态转移函数( f : S × I → S )， h 是输出函数， s 1 是初始状态。
根据输出函数 h 的不同，输入输出有限状态机可以分为Moore型自动机和Mealy型自动机两类 [11] 。
Moore型自动机是基于状态的，其输出函数为 h : S → O 。Mealy型自动机则是基于状态和输入的，其输出函数为 h : S × I → O 。
Moore型和Mealy型自动机分别如图2-5a和图2-5b所示。
图2-5 两种输入输出有限状态机
在Moore型自动机中，状态 s 在输入in之后转移到状态 s′ ，状态 s′ 下的输出为 o′ ；在Mealy型自动机中，状态 s 在输入in之后输出o，同时转移到状态 s′ 。因此，它们不仅表现形式不同，在转移和输出顺序方面也是不同的。后面例子表明它们表现的方便性和复杂性更是不同的。
在2.1.2节中几个例子是使用有限状态机进行建模的，规范了状态的转移条件，但缺少输出功能。现在增加输出功能，使之更接近于实际控制系统。
例2.4 旋转式栅门
在原系统需求的基础上增加输出功能。分两种情形建模。
解：情形1。 在刷卡成功后解锁的同时显示“请通过”，当机器锁住时显示“请刷卡”。该情形使用Moore型自动机建模。
状态集 S ={锁住，解锁}
输入集 I ={刷卡，通过}
输出集 O ={请通过，请刷卡}
状态转移函数 f : S × I → S ：
（锁住，刷卡）→解锁
（解锁，通过）→锁住
输出函数 h ： S → O ：
锁住→请刷卡
解锁→请通过
初始状态=锁住
其示意图如图2-6a所示。
图2-6 旋转式栅门的两种输入输出有限自动机
情形2 。若使用Mealy型自动机建模，则输出元素需要做调整，才能更符合实际情况。
输出集 O ={请通过，谢谢}
输出函数 h : S × I → O ：
（锁住，刷卡）→请通过
（解锁，通过）→谢谢
其示意图如图2-6b所示。
例2.5 餐巾纸售货机
一款餐巾纸售货机只接收5角和10角，1包餐巾纸价格为15角，有找零功能。
解：使用Moore型自动机建模。
状态集 S ={0角，5角，10角，15角，20角}
输入集 I ={5角，10角， X } // X 表示无输入
输出集 O ={0包，1包}
转移函数 f : S × I → S :
（0角，5角）→5角
（0角，10角）→10角
（5角，5角）→10角
（5角，10角）→15角
（10角，5角）→15角
（10角，10角）→20角
（15角， X ）→0角
（20角， X ）→0角
输出函数 h : S → O ：
15角→1包|0角
20角→1包|5角
5角→0包|0角
10角→0包|0角
0角→0包|0角
其中“1包|5角”表示同时输出“1包”和“5角”。示意图如图2-7所示。
图2-7 餐巾纸售货机Moore型自动机
使用Mealy型自动机建模 。
状态集 S ={0角，5角，10角}
输入集 I ={5角，10角}
输出集 O ={0包，1包，0角，5角}
状态转移函数 f : S × I → S ：
（0角，5角）→5角
（0角，10角）→10角
（5角，5角）→10角
（5角，10角）→0角
（10角，5角）→0角
（10角，10角）→0角
输出函数 h : S × I → O ：
（5角，5角）→0包|0角
（5角，10角）→1包|0角
（10角，5角）→1包|0角
（10角，10角）→1包|5角
示意图如图2-8所示。
例2.6 时序检测器
时序检测器在接收连续的3个1后输出1，其他情况输出0。
图2-8 餐巾纸售货机Mealy型自动机
解：使用输入输出有限状态机建模。
状态集 S ={ s 0 , s 1 , s 2 , s 3 }，其中 s 0 表示检测到0个1， s 1 表示检测到1个1， s 2 表示检测到2个1， s 3 表示检测到3个1。
输入集 I ={0,1}
输出集 O ={0,1}
转移函数 f : S × I → S ：
( s 0 ,0)→ s 0 ,( s 0 ,1)→ s 1 ,( s 1 ,0)→ s 0 ,( s 1 ,1)→ s 2
( s 2 ,0)→ s 0 ,( s 2 ,1)→ s 3 ,( s 3 ,0)→ s 0 ,( s 3 ,1)→ s 3
输出函数 h 要分成Moore型和Mealy型，用Moore型自动机和Mealy型自动机建模的时序检测器分别如图2-9和图2-10所示。
图2-9 时序检测器Moore型自动机
图2-10 时序检测器Mealy型自动机
例2.7 电梯控制系统 [12]
假设有一座有3层高的楼，装有电梯1部，每层楼都能到达。分别使用Mealy和Moore型自动机为电梯控制系统建模。
解：使用Mealy型自动机建模。
状态集 S ={ s 1 , s 2 , s 3 }，表示楼层集，如 s 3 表示第3层楼。
输入集 I ={ r 1 , r 2 , r 3 }，表示要到达的楼层，如 r 2 表示电梯要到达第2层楼。
输出集 O ={ d 2 , d 1 , n , u 1 , u 2 }。表示方向和电梯要移动的楼层，如 d 2 表示电梯下降2层， u 2 表示电梯上升2层，而 n 表示电梯保持当前楼层。
转移函数 f : S × I → S ：
( s 1 , r 1 )→ s 1 ，( s 1 , r 2 )→ s 2 ，( s 1 , r 3 )→ s 3
( s 2 , r 1 )→ s 1 ，( s 2 , r 2 )→ s 2 ，( s 2 , r 3 )→ s 3
( s 3 , r 1 )→ s 1 ，( s 3 , r 2 )→ s 2 ，( s 3 , r 3 )→ s 3
输出函数 h : S × I → O ：
( s 1 , r 1 )→ n ，( s 1 , r 2 )→ u 1 ，( s 1 , r 3 )→ u 2
( s 2 , r 1 )→ d 1 ，( s 2 , r 2 )→ n ，( s 2 , r 3 )→ u 1
( s 3 , r 1 )→ d 2 ，( s 3 , r 2 )→ d 1 ，( s 3 , r 3 )→ n
用Mealy型自动机建模的电梯控制系统如图2-11所示。
图2-11 电梯控制系统Mealy型自动机
使用Moore型自动机建模 。
Moore型自动机的输出函数只依赖于状态，因此在同一个楼层也有3种输出：上升 u 、下降 d 和空闲 n 。这样需要把每个楼层状态分成3个子状态，如将 s 1 分成 s 11 、 s 12 和 s 13 ，以便同3种输出进行组合，于是Moore型自动机就有了9种状态。
状态集 S ={ s 11 , s 12 , s 13 , s 21 , s 22 , s 23 , s 31 , s 32 , s 33 }
输出集 O ={ d 2 , d 1 , n , u 1 , u 2 }
把 S 和 O 进行笛卡儿乘积，应该得到的集合 S × O 共有45个元素，即45个由楼层和输出组成的组合状态，但不需要这么多。如对于第1层来说，输出只有空闲 n （保持在第1层）、到达1层的 d 1 （从第2层到达第1层）和 d 2 （从第3层到达第1层）。对于第2层，输出有空闲 n （保持在第2层）、上升到2层的 u 1 （从第1层上升到第2层）和下降到2层的 d 1 （从第3层下降到第2层）。而对于第3层，输出有空闲 n （保持在第3层）、上升到3层的 u 1 （从第2层上升到第3层）和 u 2 （从第1层上升到第3层）。
这样共有9个有用的组合，使用Moore型自动机建模。
状态集 S ={( s 11 / d 2 )，( s 12 / d 1 )，( s 13 / n )，( s 21 / d 1 )，( s 22 / n )，( s 23 / u 1 )，( s 31 / n )，( s 32 / u 1 )，( s 33 / u 2 )}
输出函数 h : S → O ，定义为： h ( s 11 )= d 2 , h ( s 12 )= d 1 , h ( s 13 )= n ； h ( s 21 )= d 1 , h ( s 22 )= n , h ( s 23 )= u 1 ； h ( s 31 )= n , h ( s 32 )= u 1 , h ( s 33 )= u 2
输入集 I ={ r 1 , r 2 , r 3 }
转移函数 f : S × I → S
用Moore型自动机建模的电梯控制系统如图2-12所示。
图2-12 电梯控制系统Moore型自动机
从例2.5和例2.7可以看到，Mealy型自动机包含的状态数少于Moore型自动机包含的状态数，因而常用Mealy型自动机进行建模。