第三章有穷自动机.pptVIP

第三章 有穷自动机 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。 3.1 概述——有穷自动机的意义 有穷状态自动机(Finite-state Automata FSA)或简称FA是具有离散的输入\输出系统的数学模型。系统内部具有有穷个状态，系统的状态概括了对过去输入状况的处理信息，系统只需根据当前所处的状态和面临的输入就可以决定系统的后继行为，系统处理了当前的输入后，系统的内部状态也将发生变化。电梯控制装置、文本编辑程序、编译技术中的词法分析程序，计算机以及人脑都是有穷状态系统。 3.1 概述——有穷自动机的模型 3.2 有穷自动机的形式定义 定义3.1 一个确定有穷自动机DFSA是一个五元组 M=(Q, ?, t, q0, F) 其中， Q：是非空有穷状态集,其中的每个元素称为一个状态； ?：是有穷输入字母表，它的每一个元素称为一个输入 符号； t ：是一个单值映射Q???Q，也称状态转换函数，t(q,x)=q?意指：当现行状态为q，面临的输入符号为x时，将转到下一状态q?，q?称为q的一个后继状态； q0?Q称之为开始状态； F?Q称为终止状态集，至少由一个终止状态组成。 3.2.1 状态转换表（矩阵） DFA转换矩阵: 该矩阵行表示状态集； 列表示输入字母表； 矩阵元素表示 t（q,a）的值。即某行状态面临某列输入字符所唯一转向的下一个状态。 　该矩阵称为状态转换矩阵 3.2.1 状态转换表（矩阵） 例3.1 有穷自动机 A=(Q, ?, t, q0,F) 其中，Q={ S,A,B,G,H}，?={+，-，·，d}，S是开始状态，终止状态集F={B,H}，映射t:Q???Q由下表所示的状态转换表给出。 3.2.2 状态转换图(1) 一个DFA也可表示成一张状态转换图。 DFA状态：用圆圈节点表示； 初始状态节点：用“右向双(单)箭头”表示； 终止状态节点：用“双圈”表示； 状态变迁：用单向弧线表示，上面必须标记激励变迁的符号。 3.2.2 状态转换图 例3.2 有穷自动机A(记为DFSA A)， A=(Q, ?, t, q0,F) 其中，Q={ q0, q1, q2, q3}，?={a, b}，q0是开始状态，终止状态集F={q0}，映射t:Q???Q由下图所示的状态转换图给出。 在图中，状态q0用双 圆圈标记，表明它是终止 状态；同时，用一个箭头 标记，表明它是开始状态。 3.2.3 构形和移动（1） 对于一个给定的输入串,假定一个DFSA 已经完成了若干次移动,为了预测它的进一步行为,只需要知道”当前状态”和”尚待扫描的输入串”,这两类信息对于在某一次的特定应用中,位于某个特定时刻的DFSA提供了一种完整的描述,这种描述就称为构形。 3.2.3 构形和移动（2） 构形(q0，ω)称为初始构形，其中q0是初始状态，ω是由该自动机可接收或拒绝的任何输入串。构形(q, ?)称为终止构形，其中?是空串，q?F(终态集)。 自动机的移动(记为├)是从一种构形到另一种构形的转换。 DFSA的工作过程就是一系列的移动过程。 记号├+称为├的传递闭包；├*称为├的自反闭包。 ├*表示“0次或多次移动”；├+表示“一次或多次移动”。 3.2.3 构形和移动（3） DFSA M 所识别的语言L（M）可表示为： L（M）={ω??*︱（q0,ω)├*(q,?)＆q ?F} 自动机接受(识别)字符串 1）自动机所接收字符 如果对某一自动机M=（ Q, ?, t, q0, F） x∈ ?, 有t（ q0,x）=P,且P∈ F ，则称字符x被自动机所接收。 2）自动机所接收输入串 自动机从开始状态读完全部输入串后，自动机恰好到达终止状态，则称输入串被自动机所接收。 自动机接受(收)字符串 3）自动机接收语言 自动机M所能接收的串组成一个集合，则称该集合为自动机M所能接收（识别）的语言。 用L（M）表示： L（M）＝{ω ∣ t(q0, ω)∈ F , ω ∈ ?* } 3.2.4 自动机的等价性 定义3.2 M和M?是等价的，当且仅当对每一个串x，M接收x当且仅当M?接收x。 定义3.3 如果M仅通过重新标记它的状态就能转换称M?,则M和M?称为同构的(Isomorphic)。 FSA的一个基本定理是：对每一个自动机M，存在一个等价的具有最少状态个数的自动机M?，而且对于每一个其状态个数与M?相同且等价于M?的自动机M″,必是与M?同构的。换句话