《程序设计实践4w1 有限自动机》由会员分享，可在线阅读，更多相关《程序设计实践4w1 有限自动机（31页珍藏版）》请在金锄头文库上搜索。
1、 导论第10章 有限状态自动机计算机导论与程序设计基础10.3-10.61前言 输入一个字符串，判断其是否是合法的C语言 标识符； 输入一个字符串，判断其是否是 形式( 即先输入a、再输入b、最后输入c，且输入的 a、b、c的个数相同）； 。 针对类似的字符串识别问题，建立有限状态 自动机模型，可以为分析、求解带来很大的 帮助。26.1 基本概念l什么是有限状态自动机？是一种具有离散输入/输出系统的数学 模型，简称 有限自动机。这一系统具 有任意有限数量的内部“状态”。 大量通信软件的基本工作机制都是有限 状态自动机。自动机理论在通信领域中 的应用极为广泛36.1 基本概念 自动机接受一定的输
2、入，执行一定的动 作，产生一定的结果。使用状态迁移描 述整个工作过程。 状态：一个标识，能区分自动机在不同时 刻的状况。有限状态系统具有任意有限数 目的内部“状态” 自动机的本质：根据状态、输入和规则 决定下一个状态状态 输入（激励） 规则 状态迁移46.1 基本概念 可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的 规则工作，因此叫“自动机”。56.1 基本概念例1：打电话 (自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经 历摘机，拨号，应答，进行通话等过程，话机的 状态及状态迁移如下所示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机收齐号码q
3、0:空闲状态q1:等待拨号音状态q2:可以拨号状态q3:等待应答状态q4:通话状态状态迁移状态66.1 基本概念例2：串口通信两台微机通过串口通信, 需在两台机器间建立 好连接后，才可以传递数据，可以使用有限状态 自动机，描述串口通信的状态。传输数据收到 应答 断开 连接发出连接请求q0q1q2q0：空闲状态q1: 等待应答状态q2：通信状态7 电话和串口都可抽象为有限自动机1. 对对象处于某一相对稳定的状态下；2. 某个事件（输入）发生；3. 这一事件引起一串处理发生，包括执行特定 的功能，产生相应的输出等；4. 处理结束，对象迁移到一个新的相对稳定状 态。6.1 基本概念8有限自动机示意图
4、工作原理：读头在输入带上从左向右移动，每当读 头从带上读到一个字符时，便引起控制器状态的改 变，同时读头右移一个符号的位置。组成一个有限控制器一个读头一条写有字符的输入带6.1 基本概念9 控制器包括有限个状态，状态与状态之间存在着 某种转换关系。每当在某一状态下读入一个字符 时，便使状态发生改变（称为状态转换）。 状态转换包括以下几种情况：1) 转换到其自身， 即保持当前状态不变；2) 转换的后继状态只有一 个；3) 转换的后继状态有若干个。 如果一个有限自动机每次转换的后继状态都是唯 一的，称为确定的有限自动机（DFA）；如果转 换的后继状态不是唯一的，则称为不确定的有限 自动机（NFA）
5、。 通常把有限自动机开始工作的状态称为“初始状 态”，把结束工作的状态称为“终止状态”或“接受 状态”。 6.1 基本概念10 确定的有限自动机的形式化定义确定的有限自动机是一个五元组 其中：有限的状态集合；：有限的输入字母表；： 转换函数，是 到 的映射；： 初始状态， ；： 终止状态集， ；6.1 基本概念（初始状态只有一个）11 为了描述一个有限自动机的工作状况，可采 用状态转换图状态转换图。状态转换图是一个有向图， 图中的每个节点表示一种状态，一条边（或 弧）表示一个转换关系。q0q1q3q2aabbb初始状态：q0终止状态：q3控制器的状态集合 ：q0,q1,q2,q36.1 基本概
6、念a12有限自动机的状态转换图q0q1q3q2aabbab 状态集合字母表初始状态终止状态集转换函数用于识别输入的字符串是否是 或者 形式的有限自动机。13l 存储程序的计算机本身也可以认为是一个有 限状态机。输入输出都是离散量，某时刻的 状态由当时进行的操作、寄存器、主存储器 和辅助存储器中存储内容确定。 l 一个运行中的程序在不同时刻也具有不同的 状态，程序执行中的状态就是各种“变量”当 时所存放的值。比如我们设计的求5！的程序 ，初始进入循环前的状态是：(p=1 and i=2), 执行完循环后的状态是：（p=40 and i=6）。 6.1 基本概念146.2 程序设计实例研究应用有限
7、自动机模型求解问题的核心问题就是抽象出状 态，描述出状态转移图和状态转移函数应用有限自动机解题步骤 1、确定输入集 2、确定状态 3、绘制状态迁移图 4、确定状态转移函数（在某状态下，接收到某一字符 后，自动机要执行的操作，以及迁移到的下一状态）15设计交通车辆观测统计算法。 问题描述：在一个路口设置一个探测器，通过通信线路 连接到后台的计算机。路口每通过一辆汽车，探测器 向计算机发出一个车辆信号1，探测器每隔1秒钟向 计算机发出一个时钟信号0，观测结束向计算机发出 结束信号。 要求在计算机上设计一个程序，能够接收探测器发出的 信号，统计出观测的时长、在观测时长内通过的车辆 总数、以及两辆车之
8、间最大的时间间隔。 问题分析：探测器向计算机发出的信号可以认为是一个 任意长的字符序列（以EOF结束），比如： “011011000111101”，这样设计程序实际上演变为读取该 字符序列，然后进行相关的操作。 1观测时长：字符序列中0的个数(6秒)； 车辆总数：字符序列中1的个数(9辆)； 两车间最大时间间隔：两个1之间的最大连续0的个数(3 秒)；6.2 程序设计实例研究16 重新审题：我们所设计的程序就是读入以 EOF结束的由0或者1组成的字符串，这个 字符串可以映射为有限自动机模型中的字符 输入带，我们的任务就是设计控制器程序逐 字符地读取输入带，进行处理并引起控制器 的状态改变，最终
9、产生输出，因此这个问题 的求解就抽象为一个有限自动机。6.2 程序设计实例研究17交通灯观测实例研究-解法11、确定输入集T1， 0，# 2、对输入集进行分类， 确定状态 3、绘制状态迁移图184、确定转换函数 当前状态是q0 (state=q0)： 读入1：vehicles+; state=q1 读入0：seconds+; state=q2 读入EOF： state=q3 当前状态是q1 (state=q1)： 读入1：vehicles+; 读入0：interval=1;seconds+; state=q2 读入EOF： state=q319 当前状态是q2 (state=q2)： 读入1：
10、if(vehicles0) 处理最大时长vehicles+; state=q1 读入0：seconds+; if(vehicles0) interval+; 读入EOF： state=q3终止状态集F=q320有限自动机解题通用处理模式解法2对应代码：解法1对应代码：此处自动机 会有不同处 理21交通灯观测实例研究-解法21、确定输入集T1，0，# 2、对输入集进行分类，确定状态: 0n此前从未出现1：若接收到这样的0,则系统进 入状态 q1n此前出现过1 ：若接收到这样的0,则系统进入 状态 q2 1n这是第一个1：进入状态 q3n这不是第一个1，且前面是0：进入状态 q4n这不是第一个1，
11、且前面是1:进入状态 q5 #n进入结束状态 q622交通灯观测实例研究-解法23、绘制状态迁移图说明：在q0q4 的任何一个状态 下，如果接收到 字符#,则进入 终止状态q6。此 处为了保持图的 简洁，没有画出 到q6的迁移。23交通灯观测实例研究-解法24、确定状态转移函数 当前状态是q0n读入1：vehicles+; state=q3n读入0：seconds+; state=q1n读入# ： state=q6 当前状态是q1n读入1：vehicles+; state=q3n读入0：seconds+; n读入# ： state=q624交通灯观测实例研究-解法24、确定状态转移函数（续）
12、当前状态是q3n读入1：vehicles+; state=q5n读入0：seconds+; interval+;state=q2n读入# ： state=q6 当前状态是q5n读入1：vehicles+; n读入0： seconds+; interval+;state=q2n读入# ： state=q625交通灯观测实例研究-解法24、确定状态转移函数（续） 当前状态是q2n读入1：vehicles+； if(intervallongest) longest=interval;interval=0; state=q4n读入0：seconds+; interval+;n读入# ： state=q
13、6 当前状态是q4n读入1：vehicles+; state=q5n读入0： seconds+; interval+; state=q2n读入# ： state=q6266.2 程序设计实例研究例2 检验输入是否是合法的C语言注释/*/q1:等待*状态q2：注释开始状态q3: 等待/以结束注 释状态q4：已接收注释结 束状态276.2 程序设计实例研究转换函数分析 start状态下：n输入/:state=q1n输出非/:state=ERROR q1状态下：n输入*:state=q2n输出非*:state=ERROR q2状态下：n输入*:state=q3n输入EOF：state=ERRORn输出其他: state=q2286.2 程序设计实例研究 转换函数分析(续） q3状态下：n输入*:状态不变n输入/:state=q4n输入EOF： state=ERRORn输出其他: state=q2 q4状态下：n输入EOF： state=ACCEPTn输出其他: state=ERROR296.2 程序设计实例研究 例3 去除C语言注释3031
