北邮-有限状态机应用

1用有限状态自动机模型解题2什么是有限状态自动机？FiniteStateMachine,又称有限状态机或简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。–状态：存储关于过去的信息，就是说,它反映从系统开始到现在时刻的输入变化。–转移:指示状态变更，并且用必须满足来确使转移发生的条件来描述它。–动作:是在给定时刻要进行的活动的描述。有多种类型的动作：进入动作（Entryaction）-在进入状态时进行退出动作-在退出状态时进行输入动作-依赖于当前状态和输入条件进行转移动作-在进行特定转移时进行3•为了描述一个有限状态机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表示一个转换关系。•初始状态通常用“没有起点的箭头”指向它来表示。•终止状态是机器完成了它的程序之后的状态，它通常表示为双重圆圈。q0q1q3q2aabbb状态转换图a4状态表•除了状态转换图以外,还可以使用多种类型的状态转移表。最常见的表示如下：•当前状态和条件的组合指示出下一个状态。•完整的动作信息可以只使用脚注来增加。状态转移表当前状态→条件↓状态A状态B状态C条件X………条件Y…状态C…条件Z………5•FSM有两个不同的类别：接受器／识别器和变换器。•接受器产生一个二元输出，说要么“是”要么“否”来回答输入是否被机器接受。•在所有输入都被处理了的时候，如果当前状态是接受状态，输入被接受；否则被拒绝。•作为规则，输入是符号（字符）；动作不使用。接受器状态机q0q1q3q2aabbbErr6•变换器使用动作基于给定输入和／或状态生成输出。常分为两种类型：Moore机和Mealy机。•Moore机-只使用进入动作的FSM，就是说输出只依赖于状态。Moore模型的好处是行为的简单性。•例：一个电梯门的MooreFSM。状态“Opening”中的进入动作(E:)开启电机开门，在状态“Closing”中的进入动作以反方向开启电机关门。状态“Opened”和“Closed”不进行任何动作。变换器状态机（1）q0openingcloseing开门关门openedclosed7•Mealy机-只使用输入动作的FSM，就是说输出依赖于输入和状态。•MealyFSM的使用经常导致状态数目的简约。•例：电梯门的MealyFSM•有两个输入动作：“开启电机关门如果command_close下达”和“反向开启电机开门如果command_open下达”。变换器状态机（2）q0openedclosed8FSM的类型•在实践中经常使用混合模型。•进一步可区分为确定型（DFA）和非确定型（NDFA、GNFA）自动机。在确定型自动机中，每个状态对每个可能输入只有精确的一个转移。在非确定型自动机中，给定状态对给定可能输入可以没有或有多于一个转移。•这个区分在实践而非理论中更有用，因为存在算法把任何NDFA转换成等价的DFA，尽管这种转换一般会增加自动机的复杂性。9有限状态自动机的应用•有限状态自动机在很多不同领域中都是重要的，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。•针对许多类型的编程问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。10例1：串口通信两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接发出连接请求q0q1q2q0：空闲状态q1:等待应答状态q2：通信状态11例2：打电话(状态机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机q0:空闲状态q1:等待拨号音状态q2:可以拨号状态q3:等待应答状态q4:通话状态状态迁移状态12•接受器有限状态机的形式化定义一个五元组其中：：有限的状态集合；：有限的输入字母表；：转换函数，是到的映射；：初始状态，；：终止状态集，；QT0qFTQQQF接受器的形式化定义Qq0),,,,(0FqTQM（初始状态只有一个）13aq0q1q3q2aabbb状态集合字母表初始状态终止状态集},,,{3210qqqqQ},{baT}{3qF0q转换函数10),(qaq20),(qbq31),(qaq11),(qbq22),(qaq32),(qbq),(3aq),(3bq例3:用于识别输入的字符串是否是或者形式的有限自动机。aabnbban14程序设计实例研究应用有限状态机模型求解问题，关键就是抽象出状态，描述出状态转移图和状态转移函数应用有限状态机解题步骤1、确定输入集2、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，确定下一个状态）3、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态）15程序设计实例研究例4检验输入是否是合法的C语言注释/*…*/导论教材P172,图10.10,注意读程序实例startq1q2q3/**/Accept*otherothererrorotherotherEOFEOFq4EOFotherq1:等待*状态q2：注释开始状态q3:等待/以结束注释状态q4：已接收注释结束状态16程序设计实例研究•转换函数分析–start状态下：输入‘/’:state=q1输出非‘/’:state=ERROR–q1状态下：输入‘*’:state=q2输出非‘*’:state=ERROR–q2状态下：输入‘*’:state=q3输入EOF：state=ERROR输出其他:state=q2176.2程序设计实例研究•转换函数分析(续）–q3状态下：输入‘*’:状态不变输入‘/’:state=q4输入EOF：state=ERROR输出其他:state=q2–q4状态下：输入EOF：state=ACCEPT输出其他:state=ERROR186.2程序设计实例研究•例5去除C语言注释startq1q2q3/**/*other非/和*q5/q4非/和*/其他非\n其他\nendEOFEOF在q1状态下，如果读取的字符不是*和/,则先要往文件中写入/,再写入读取的字符19有限状态机解题通用处理模式有限状态机解题通用处理模式state!=ENDstate=START读入一字符根据当前状态、当前读入的字符，进行处理，并决定下一状态初始化输出结果#defineSTART1...intstate=START;...while(state!=END){ch=getch();switch(state){caseSTART:if(ch==?)state=Q1;break;...}20为什么要用状态机?有限状态机到底有什么好处？怎样才算应用状态机解题？1、状态机用数学模型来设计解题思路，准确可靠、简练，而程序员仅仅依靠自己的脑力和复杂的程序结构。2、状态机模型的思路和人解决问题的思路是一致的，都是把复杂的问题逐步分解为简单的步骤。所以状态机模型是程序员的好助手，不是你的竞争对手。3、状态机解题的特征：在连续输入的逻辑判断过程中，有清楚的状态分段，各状态段之间的逻辑跳转有严谨的迁移规则。4、应用状态机设计的程序最终表现出的清晰严谨的逻辑结构，而不是可读性很差的“聪明”代码。21•例6:输入一个字符串，以’#’结束，要求判断其是否满足anbncn形式。程序运行效果如下：例1：Pleaseinputstringconsistofa/b/c,'#'toend:aabbcc#thestringisacceptable例2：Pleaseinputstringconsistofa/b/c,'#'toend:aabbc#thestringisnotacceptable22为什么要引入状态?-问题示例main(){intcount1=0,count2=0,count3=0;charch;ch=getch()while(ch==‘a’){count1++;ch=getch();}while(ch==‘b’){count2++;ch=getch();}while(ch==‘c’){count3++;ch=getch();}if(ch==‘#’){if(count1==count2)&&(count2==count3)printf(“stringisacceptable!\n”);elsestringisnotprintf(“acceptable!\n”);}system(“pause”);return0;}初始化状态1getch=‘a’getch=‘a’状态2getch=‘b’getch=‘b’状态3getch=‘c’getch=‘c’状态4getch=‘#’正确错误返回首字母不是a/b/c/#getch不是a/b/c/#导论教材P168图10.6程序实例不是好的状态机实例，同学不要学！23上机作业•作业：（实验指导书-实验12-第10题）–输入一个字符串，长度不超过1000，以回车结束，要求判断其是否属于规则表达式。–一级表达式::=变量一级运算符变量–变量::=字母|字母变量–一级运算符::=|==||=|=–二级表达式::=一级表达式&&一级表达式–三级表达式::=二(一)级表达式||二(一)级表达式•第5周上机实验完成•1-5班第5周周日上午8:30-11:30•16-19班第5周周日下午1:30-4:3024