第2章 有限状态机FSM

有限状态机FiniteStateMachine刘靖[e-mail]2012-10-8有限状态机的产生现实世界中，存在大量具有有限个状态的系统◦钟表系统◦电梯系统◦通信协议系统有限状态机的概念来自于现实世界中的这些有限系统，是关于存储量有限的计算机的基本模型，也是许多形式化规约描述和验证技术的基础模型2实际例示–自动门控制器3状态：Closed/Open动作：◦Front（前缓冲区有人）、Rear（后缓冲区有人）◦Both（前后都有人）、Neither（前后都没人）抽象表示一个状态机包括如下几个部分：有限状态集合：描述系统处于的不同状态输入符号集：描述系统接收的不同输入信息状态转移规则：描述系统接收不同输入信息时，从一个状态转移到另一个状态的规则4FSM的形式定义有限状态机是一个五元组M=(Q，∑，，q0，F)，其中Q={q0，q1，…，qn}是有限状态集合。在任一确定的时刻，有限状态机只能处于一个确定的状态qi；∑={1，2，…，m}是有限输入字符集合。在任一确定的时刻，有限状态机只能接收一个确定的输入j；：QQ是状态转移函数。在某一状态下，给定输入后有限状态机将转入状态迁移函数决定的一个新状态；q0∈Q是初始状态，有限状态机由此状态开始接收输入；FQ是终结状态集合，有限状态机在达到终态后不再接收输入。5状态转移函数的表示方式状态转移矩阵状态转移表状态转移图6M=({q0，q1，q2，q3},{0,1},,q0,{q0})重要概念–字符串有限字母表∑：由有限个字符组成的非空集合◦键盘上的字母、数字、运算符、标点符号等字符串：由字符组成的有限序列，常用小写希腊字母表示字母表∑上的字符串的生成方式：◦(1)ε为∑上的一个特殊串，称为空串，∀a∈∑:aε=εa=a◦(2)若σ为∑上的字符串，且a∈∑，则σa或aσ是上∑的字符串◦(3)若α为∑上的字符串，当且仅当它由（1）和（2）导出直观的说，∑上的字符串是由其上的符号以任意次序拼接起来构成的，任何符号都可以在串中重复出现◦例如：∑={a，b}时，aabb,ab,abba,bba,ε等都是其上的字符串字符串的操作：长度(|α|)、连接(α·β)、重复连接(α3)7重要概念–语言语言L：给定字母表∑上的字符串的集合◦例如：∑={a，b}时，{aabb,ab,abba},{ε},{anbn|n≥1}等都是∑上的语言不包含任何字符串的语言称为空语言Ф◦注意：{ε}与Ф是不同的字母表∑上的所有字符串（包括空串）所构成的语言集表示为∑*有限状态机所接受的语言，显然L⊆∑*L(M)={x|(q0,x)∈F,x∈∑*}有限状态机所接收的语言也就是其所对应行为的字符串集8例子状态S1表示在输入的字符串中有偶数个0，状态S2表示有奇数个0；输入1不改变自动机状态L(M)={(1*(01*0)*)*}当读完输入的字符串的时候，状态将显示输入的字符串是否包含偶数个09重要概念–扩展的状态转移函数对一个有限状态机M=(Q，∑，，q0，F)，它的扩展转移函数’为：Q*Q：◦’(q,ε)=q◦’(q,wσ)=(’(q,w),σ)其中，q∈Q,w∈*,σ∈实际上，’(q,x)就是从q出发，用原来的状态转移函数，每经过x中的一个符号后改变一次状态，直到经过最后一个符号后所到达的状态10带输出的有限状态机现实生活中的许多有限状态系统，对于不同的输入信息，除内部状态不断改变外，还不断向系统外部输出各种信息按输出的不同，有限状态机分为两类：Moore机Mealy机（输出仅与状态有关）（输出与状态和输入都有关）11Moore机Moore机是六元组M=(Q，∑，Δ，，λ，q0)其中：Q={q0，q1，…，qn}是有限状态集合∑={1，2，…，m}是有限输入字符集合Δ={a1，a2，…，ar}是有限输出字符集合：QQ是状态转移函数λ：QΔ是输出函数q0∈Q是初始状态1.Moore机只是在接收输入串的过程中不断改变状态，并且在每个状态上有字符输出，不存在终止状态；2.不带输出的有限状态机可看做是Moore机的特例（为什么）12Moore机实例131.theoutputistheXORofthetwomost-recentinputvalues2.themachineimplementsanedgedetector,outputtingaoneeverytimetheinputflipsandazerootherwiseMealy机14Moore机是六元组M=(Q，∑，Δ，，λ，q0)其中：Q={q0，q1，…，qn}是有限状态集合∑={1，2，…，m}是有限输入字符集合Δ={a1，a2，…，ar}是有限输出字符集合：QQ是状态转移函数λ：QΔ是输出函数q0∈Q是初始状态1.Mealy机是在接收输入串的过程中不断改变状态，同时有字符输出，也不存在终止状态；2.输入串长度为n时，输出n个字符（Moore机输出几个？）Mealy机实例151.theoutputistheXORofthetwomost-recentinputvalues2.themachineimplementsanedgedetector,outputtingaoneeverytimetheinputflipsandazerootherwise确定或非确定的有限状态机非确定意味着对于任何输入符号，它的下一个状态不是唯一确定的，可以是多个可能状态中的任何一个。因此在其形式定义中，一般都使用状态幂集的子集任一个非确定有限状态机都可以转换为行为等价的确定有限状态机—接收相同的语言—PowerSetConstruction16DeterministicFSM状态转移函数：QQNon-DeterministicFSM状态转移函数：Q2Q有限状态机的化简对于一个确定的有限状态机，我们希望能够找到一个与之等价且状态数极小的有限状态机将状态集合划分为等价类，一个等价类中的任何状态，对于所有输入字符的状态转移，都归属到另一个等价类中，这样我们就可以把状态的等价类看做一个状态，从而实现有限状态机的化简，或称为最小化过程17有限状态机的合并（叉乘）叉乘：多个有限状态机的合并，有三种方式：1.笛卡尔积：描述了多个有限状态机相互独立运行的行为2.同步积：描述了多个有限状态机的耦合运行，阻止各自的独立运行行为3.异步积：描述了多个有限状态机的耦合运行，但任何状态下允许其中一个状态独立执行18生产者-消费者问题的FSM建模19生产者-消费者问题的FSM建模20有限状态机的局限性有限状态机的叉乘很容易导致状态爆炸有限状态机模型实质上存在一个限制性假设：在系统所处的每一个状态上，在任何时刻，最多执行一个操作。因此，有限状态机仅能够描述顺序系统，无并发行为的描述能力有限状态机为了描述无限系统、时间特性、层次结构等特性需要进行扩展21习题：使用FSM对下述系统建模1、哲学家问题2、交叉位协议系统3、自选软件系统22