10程序设计实践4w1 有限自动机C语言版
前言 输入一个字符串，判断其是否是合法的C语言标识符； 输入一个字符串，判断其是否是 形式(即先输入a、再输入b、最后输入c，且输入的a、b、c的个数相同)； 。。。 针对类似的字符串识别问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。 6.1 基本概念 什么是有限状态自动机？ 是一种具有离散输入/输出系统的数学模型，简称 有限自动机。这一系统具有任意有限数量的内部“状态”。 大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛 6.1 基本概念 自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。 状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态” 自动机的本质：根据状态、输入和规则决定下一个状态 状态 ＋ 输入(激励)＋ 规则 ―> 状态迁移 6.1 基本概念 可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。 6.1 基本概念 例1：打电话 (自动机在通信领域的应用)。 在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。 6.1 基本概念 例2：串口通信 两台微机通过串口通信, 需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。 6.1 基本概念 电话和串口都可抽象为有限自动机 ? 1. 对象处于某一相对稳定的状态下； 2. 某个事件(输入)发生； 3. 这一事件引起一串处理发生，包括执行特定 的功能，产生相应的输出等； 4. 处理结束，对象迁移到一个新的相对稳定状态。 6.1 基本概念 6.1 基本概念 控制器包括有限个状态，状态与状态之间存在着某种转换关系。每当在某一状态下读入一个字符时，便使状态发生改变(称为状态转换)。 状态转换包括以下几种情况：1) 转换到其自身，即保持当前状态不变；2) 转换的后继状态只有一个；3) 转换的后继状态有若干个。 如果一个有限自动机每次转换的后继状态都是唯一的，称为确定的有限自动机(DFA)；如果转换的后继状态不是唯一的，则称为不确定的有限自动机(NFA)。 通常把有限自动机开始工作的状态称为“初始状态”，把结束工作的状态称为“终止状态”或“接受状态”。 6.1 基本概念 确定的有限自动机的形式化定义 确定的有限自动机是一个五元组 其中： ：有限的状态集合； ：有限的输入字母表； ： 转换函数，是 到 的映射； ： 初始状态， ； ： 终止状态集， ； 6.1 基本概念 为了描述一个有限自动机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边(或弧)表示一个转换关系。 用于识别输入的字符串是否是 或者 形式的有限自动机。 6.1 基本概念 存储程序的计算机本身也可以认为是一个有限状态机。输入输出都是离散量，某时刻的状态由当时进行的操作、寄存器、主存储器和辅助存储器中存储内容确定。 一个运行中的程序在不同时刻也具有不同的状态，程序执行中的状态就是各种“变量”当时所存放的值。比如我们设计的求5！的程序，初始进入循环前的状态是：(p=1 and i=2), 执行完循环后的状态是：(p=40 and i=6)。 6.2 程序设计实例研究 应用有限自动机模型求解问题的核心问题就是抽象出状态，描述出状态转移图和状态转移函数 应用有限自动机解题步骤 1、确定输入集 2、确定状态 3、绘制状态迁移图 4、确定状态转移函数(在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态) 6.2 程序设计实例研究 设计交通车辆观测统计算法。 问题描述：在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号‘1’，探测器每隔1秒钟向计算机发出一个时钟信号‘0’，观测结束向计算机发出结束信号‘＃’。 要求在计算机上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。 6.2 程序设计实例研究 重新审题：我们所设计的程序就是读入以EOF结束的由‘0’或者‘1’组成的字符串，这个字符串可以映射为有限自动机模型中的字符输入带，