有限自动机理论CH3PART1.ppt

第三章 有限状态自动机 定义语言 可以从两个方面进行： １）从产生语言的角度； ２）从接收(或识别)语言的角度。 形式语言研究内容 产生一个语言: 1)定义语言中的基本句子; 2)根据其余句子的形成规则，产生出该语言所包含的所有句子。 有限自动机研究内容 使用某种自动机模型来接收字符串 接收的所有字符串形成的集合，也是一个语言 统一的理论 形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言) 3) 形式语言与自动机的等价性理论 有限状态自动机 FA(Finite state Automaton) FA是为研究 有限存储的计算过程 正则语言 而抽象出的一种计算模型。 两类有限状态自动机 接收器 判断是否接收输入串； 转换器 对给定输入产生输出。 FA还可以分成确定（DFA）与非确定（NFA）两种。 等价性 有限状态自动机识别的语言称为有限状态语言--FSL. 从产生语言角度而言， FSL就是右线性语言--RLL 从正则运算角度而言， FSL就是正则语言--RL。 有限状态自动机除了它在理论上的价值外， 还在数字电路设计、词法分析、文本编辑程序等领域得到广泛应用 3.1 有限状态自动机 有限状态自动机是具有离散输入和输出系统的一种数学模型。 有限状态自动机物理模型 一个输入存储带（输入带），带被分解为单元，每个单元存放一个输入符号(字母表上的符号)。 整个输入串从带的左端点开始存放，而带的右端可以无限扩充； 一个有穷状态控制器（FSC） 该控制器的状态只能是有限多个 FSC通过一个读头读出当前带上单元的字符。 初始时，读头对应带的最左单元，每读出一个字符，读头向右自动移动一个单元。 读头(暂时)不允许向左移动。 有限状态自动机的一个动作为： 读头读出带上当前单元的字符 FSC根据当前FSC的状态和读出的字符，进行状态改变； 将读头向右移动一个单元。 有限态自动机的动作简化为： FSC根据 当前状态 和 当前读取的带上字符 进行状态改变。 定义3-1 有限状态自动机FA FA是一个五元式 FA=(Q，∑，δ，q0，F) Q是有限状态的集合 ∑是字母表，也就是输入带上的字符的集合； q0∈Q是开始状态； F?Q是接收状态(终止状态)集合； δ是Q×∑→Q的状态转换函数， 即δ(q，x)= q′ 代表自动机在状态q时，扫描字符x后到达状态q′ 有限状态自动机的状态转换函数的个数应该为 |Q|*|∑| 对于Q中的每个状态，都应该定义对应∑的每个字母的状态转换。 DFA 这种有限状态自动机为确定的有限状态自动机DFA。 例3-1 DFA=({q0,q1},{0,1},δ,q0,{q0}) 其中δ： δ的表示：函数形式 δ(q0，0)=q1 δ(q0，1)=q1 δ(q1，0)= q1 δ(q1，1)= q0 δ的表示：状态矩阵 Q ∑ δ的表示:状态图形式 状态图是一个有向、有循环的图 一个节点表示一个状态；若有δ(q，x)= q′，则 状态q到状态q′有一条有向边，并用字母x作标记。 δ的表示 ‘→’指向的状态是开始状态 两个圆圈代表接收状态； δ的表示：状态图 用状态图表示一个DFA 有向边的数目就是状态转换函数的个数。 3.2 有限状态自动机识别语言 对于DFA，给定串w=x1x2…xn； 初始时， DFA处于开始状态q0 从左到右逐个字符地扫描串w 在δ(q0，x1)= q1的作用下 DFA处于状态q1 在δ(q1，x2)=q2的的作用下 DFA处于状态q2 … 当将串w扫描结束后， 若DFA处于某一个接收状态， 则有限状态自动机能够接收串w 对于可接收串 DFA从开始状态开始，在扫描串的过程中， 状态逐个地变化,串扫描结束后， 到达某个接收状态。 对于不可接收串 DFA从开始状态开始，在扫描串的过程中， 状态逐个地变化,串扫描结束后， 处于非接收状态。 对于字母表∑上的DFA 能识别的所有串的集合，就是 DFA能接收的语言:L(DFA) 也称为有限状态语言（FSL） 思考 如何形式化定义L(DFA)? 定义3-4 扩展的状态转换函数 给定DFA，扩展的状态转换函数δ*：Q×∑*→Q 即