有限状态机

第五讲有限状态机2020/2/9通信软件设计第2页1.有限状态机的基本概念2.有限状态机编程方法主要内容2020/2/9通信软件设计第3页状态机的引入状态机理论最初的发展在数字电路设计领域。在数字电路方面，根据输出是否与输入信号有关，状态机可以划分为Mealy型和Moore型状态机。Moore型状态机的输出只和当前状态有关，和输入无关。Mealy型状态机的输入是由当前状态和输入共同决定。而在软件设计领域，状态机的理论俨然已经自成一体，它经常用来描述一些复杂的算法，表明一些算法的内部的结构和流程，更多的关注于程序对象的执行顺序。2020/2/9通信软件设计第4页静态顺序结构动态结构2020/2/9通信软件设计第5页有限状态机有限自动机（FiniteAutomataMachine）是计算机科学的重要基石，它在软件开发领域内通常被称作有限状态机（FiniteStateMachine），是一种应用非常广泛的软件设计模式。有限状态机的作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在现实中，有许多事情可以用有限个状态来表达，如:红绿灯、电话机等等。其实，在资讯领域中，很多事情都是由有限的状态所组成，再由于不同的输入而衍生出各个状态。2020/2/9通信软件设计第6页有限状态机有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。2020/2/9通信软件设计第7页有限状态机—例1红绿灯红绿灯运作的原理相当简单，从一开始绿灯，经过一段时间后，将变为黄灯，再隔一会儿，就会变成红灯，如此不断反覆。其FSM如下。2020/2/9通信软件设计第8页有限状态机—例2自动贩售机假设有简单的一自动贩卖机贩售两类商品，一类售价20元，另一类售价50元。如果该贩卖机只能辨识10元及50元硬币。一开始机器处于Hello的状态，当投入10元时，机器会进入余额不足的状态，直到投入的金额大于20元为止。如果一次投入50元，则可以选择所有的产品，否则就只能选择20元的产品。完成选择后，将会卖出商品并且找回剩余的零钱，随后，机器又将返回初始的状态。其FSM如下。2020/2/9通信软件设计第9页基本概念在描述有限状态机时，常会碰到的几个基本概念：状态（State）指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。事件（Event）指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。转换（Transition）指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。动作（Action）指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。2020/2/9通信软件设计第10页有限状态机模型通信协议建模基本出发点：认为通信协议主要是由响应多个“事件”的相对简单的处理过程组成。状态转移图优点：简单明了，比较精确。缺点：对许多复杂的协议，事件数和状态数会剧增，处理困难。2020/2/9通信软件设计第11页为什么使用有限状态机在面向对象的软件系统中，一个对象无论多么简单或者多么复杂，都必然会经历一个从开始创建到最终消亡的完整过程，这通常被称为对象的生命周期。对象在其生命期内是不可能完全孤立的，它必须通过发送消息来影响其它对象，或者通过接受消息来改变自身。2020/2/9通信软件设计第12页为什么使用有限状态机在银行客户管理系统中，客户类（Customer）的实例在需要的时候，可能会调用帐户（Account）类中定义的getBalance()方法。在这种简单的情况下，类Customer并不需要一个有限状态机来描述自己的行为，主要原因在于它当前的行为并不依赖于过去的某个状态。并不是所有情况都会如此简单，事实上许多实用的软件系统都必须维护一两个非常关键的对象，它们通常具有非常复杂的状态转换关系，而且需要对来自外部的各种事件进行响应。例如，在VoIP电话系统（找状态图）中，电话类（Telephone）的实例必须能够响应来自对方的随机呼叫，来自用户的按键事件，以及来自网络的信令等。在处理这些消息时，类Telephone所要采取的行为完全依赖于它当前所处的状态，此时使用状态机将是一个不错的选择。2020/2/9通信软件设计第13页为什么使用有限状态机游戏引擎是有限状态机最为成功的应用领域之一，由于设计良好的状态机能够被用来取代部分的人工智能算法，因此游戏中的每个角色或者器件都有可能内嵌一个状态机。考虑RPG（Role-playingGame）游戏中城门这样一个简单的对象，它具有打开（Opened）、关闭（Closed）、上锁（Locked）、解锁（Unlocked）四种状态。当玩家到达一个处于状态Locked的门时，如果此时他已经找到了用来开门的钥匙，那么他就可以利用它将门的当前状态转变为Unlocked，进一步还可以通过旋转门上的把手将其状态转变为Opened，从而成功进入城内。2020/2/9通信软件设计第14页控制城门的状态机2020/2/9通信软件设计第15页1.有限状态机的基本概念2.有限状态机编程方法主要内容2020/2/9通信软件设计第16页确定的有限状态机一个DFAM是一个五元组，记作M=(S,,f,S0,Z)，其中1)S={状态i}，S是一个有限集，其中的每一个元素称为一个状态2)={输入字符i}，是一个有穷字母表，它的每一个元素称为一个输入字符3)f:S×→S，f是转换函数，表示某状态接受某个输入字符所到达的状态，如：f(p,a)=q，p，qS，a4)S0S，S0是S中的元素，是唯一的一个初态5)ZS，且Z，Z是S的一个子集，是一个终态集，或叫结束集2020/2/9通信软件设计第17页确定的有限状态机左侧的状态图，在数学上称作DFA，其形式化定义为：M=(S,,f,S0,Z)其中，S={0,1,2,3}={a,b,c,d}S0=0Z={3}源状态输入目的状态0a10C21d11b32d3f:013abcdd22020/2/9通信软件设计第18页手工编写状态机与其他常用的设计模式有所不同，程序员想要在自己的软件系统中加入状态机时，必须再额外编写一部分用于逻辑控制的代码，如果系统足够复杂的话，这部分代码实现和维护起来还是相当困难的。在实现有限状态机时，使用switch语句是最简单也是最直接的一种方式，其基本思路是为状态机中的每一种状态都设置一个case分支，专门用于对该状态进行控制。学习doorFSM工程，如何编程实现有限状态机。2020/2/9通信软件设计第19页手工编写状态机在很长一段时期内，使用switch语句一直是实现有限状态机的唯一方法，甚至像编译器这样复杂的软件系统，大部分也都直接采用这种实现方式。但之后随着状态机应用的逐渐深入，构造出来的状态机越来越复杂，这种方法也开始面临各种严峻的考验。如果状态机中的状态非常多，或者状态之间的转换关系异常复杂，那么简单地使用switch语句构造出来的状态机将是不可维护的。2020/2/9通信软件设计第20页doorFSM程序实例（1）新建一个Win32ConsoleApplication的简单应用程序，并利用ClassWiard建立doorFSM类，用doorFSM实现状态机。（2）编写doorFSM.h头文件（3）编写doorFSM.cpp源程序添加状态、事件、转化函数等（4）添加测试程序Test.cpp2020/2/9通信软件设计第21页DoorFSM类classDoorFSM{public:enumEvent{Lock,Unlock,Open,Close};//Eventsprotected:voidenterOpened();voidenterLocked();voidenterUnlocked();voidenterClosed();public:enumStates{Closed,Unlocked,Locked,Opened};//statesStatesdoorState;public:DoorFSM(){doorState=Opened;}//Constructorvirtual~DoorFSM(){}//DestructorStatescurrentState(){returndoorState;}//GetcurrentFSMstate,returnscurrentFSMstatevoidprocessEvent(Evente);//performeventstaticconstchar*eventName(Evente);//Getsymbolicnameofaneventstaticconstchar*stateName(Statess)；//Getsymbolicnameofastate};2020/2/9通信软件设计第22页doorFSM.cpp实现文件voidDoorFSM::processEvent(Evente){StatesyOld=doorState;boolpass=false;switch(yOld){//transitionscaseClosed:if(e==Open){//outcomeactionsdoorState=Opened;pass=true;}elseif(e==Lock){//outcomeactionsdoorState=Locked;pass=true;}break;caseUnlocked:if(e==Lock){//outcomeactionsdoorState=Locked;pass=true;}elseif(e==Open){//outcomeactionsdoorState=Opened;pass=true;}break;caseLocked:if(e==Unlock){//outcomeactionsdoorState=Unlocked;pass=true;}break;2020/2/9通信软件设计第23页自动生成状态机为实用的软件系统编写状态机并不是一件十分轻松的事情，特别是当状态机本身比较复杂的时候尤其如此。人们开始尝试开发一些工具来自动生成有限状态机的框架代码，而在Linux下就有一个挺不错的选择──FSME（FiniteStateMachineEditor）。FSME是一个基于Qt的有限状态机工具，它能够让用户通过图形化的方式来对程序中所需要的状态机进行建模，并且还能够自动生成用C++或者Python实现的状态机框架代码。2020/2/9通信软件设计第24页可视化的FSME2020/2/9通信软件设计第25页状态机建模首先运行fsme命令来启动状态机编辑器，然后单击工具栏上New按钮来创建一个新的状态机。FSME中用于构建状态机的基本元素一共有五种：事件（Event）、输入（Input）、输出（Output）、状态（State）和转换（Transition），在界面左边的树形列表中可以找到其中的四种。2020/2/9通信软件设计第26页小结在面向对象的软件系统中，有些对象具有非常复杂的生命周期模型，使用有限状态机是描述这类对象最好的方法。作为一种软件设计模式，有限状态机的概念虽然不算复杂，实现起来也并不困难，但它的问题是当状态机的模型复杂到一定的程度之后