自动机基础课件.ppt

第3章 自动机基础,自动机是一种语言模型，是语言的一种识别工具，其中的 有限自动机(Finite Automata) FA 被用来处理正规语言，后者是编译程序设计中词法分析的对象3.1 正规语言及其描述方法 3.2 有限自动机的定义与分类 3.3 有限自动机的等价转换 3.4 有限自动机的实现 3.5 正规语言描述方法间的相互转换,,,,3.1 正规语言及其描述方法,【定义】 正规语言是指由正规文法定义的语言；程序设计语言中的单词，大都属于此种语言例3.1】 G(Z)：A -aA| , A= ;,A=aA=aaA=aaaA==an ,n0, L(G)= an | n0 ,正规文法,正规语言,,,,, 正规语言判定示例:,【例3.2】 L1 = ambn| m0 ,n1 , 正规语言? 可由正规文法定义： G1(S): S - aS|bA ; A - bA| L1 是正规语言例3.3】 L2 =(ab)n| n1 , 正规语言 ? 可由正规文法定义： G2(S): S - aA ; A - bB ; B - aA| L2 是正规语言例3.4】 L3 =anbn| n0 , 正规语言 ? 不能由正规文法定义(正规文法无法描述a和b数量上相等！)： L3 不是正规语言！,,,3.1.1 正规语言的另外两种表示方法,. 正规式表示法：, 正规式是指由字母表中的符号，通过以下三种运算(也可以使用圆括号)连接起来构成的表达式 e ：,闭包( *，+) 连接 ( .) 或( | ), 设 val(e),L(e) 分别表示正规式 e 的值和语言，则：,L(e)= x| x=val(e),即 正规式表示的语言是该正规式所有值的集合。

正规式,,L3= abnc, bn | n0 ，,,,L2= (ab)n| n1 ，,e2=(ab)+,e3= ab*c|b*,L1= ambn| m0 ,n1 ，,e1= a*b+,,,,,,,,. 有限自动机表示法：,L3= abnc ,bn|n0 ,FA1:,FA2:,FA3:, 初看起来，有限自动机是带标记的有向图！,3.1.1 正规语言的另外两种表示方法,,1,2,3,4 状态集; 其中： +(开始状态)；-(结束状态) a,b,c 字母表； (1,a)=2 变换 ( 或 ); (表示1状态遇符号a变到2状态,)；,有限自动机表示法说明：,L3= abnc ,bn|n0 ,一个FA，若存在一条从某开始状态 i 到某结束状态 j 的通路，且这条通路上所有边的标记连成的符号串为，则就是一个句子；所有这样的的集合，就是该 FA 表示的语言图符说明】：,【运行机制】：,FA:,,e = ab*c|b*,,G(S): S- aA|bB| ，A - bA|c ，B - bB| ,, 正规语言的三种表示法综合示例：,【例3.5】 L = abnc, bn| n0 ,= a,b,c；,【注】凡是能由上述三种方法中的一种表示的语言， 一定是正规语言；反之，凡是不能由上述三种方法表示 的语言，一定不是正规语言。

1. 正规文法描述：,2. 正规式描述:,3. 有限自动机描述：,,,3.2.1 有限自动机的定义,,状态 i 遇符号 a 时变换为状态 j,3.2 有限自动机的定义和分类, 变换(二元函数) ;,Q(有限状态集) ;,或,(i , a)= j,其中：,i , jQ, a+;,F(结束状态集, F Q) ;,S(开始状态集, S Q) ;,(字母表) ;,,即：,,,L(FA)= x| i j , x* ,iS,jF ,FA 存在一条从某初始状态 i 到某结束状态 j 的连 续变换，且每次变换(=)的边标记连成的符号串恰好为 x ；称x为FA接受，否则拒绝令L(FA)为自动机FA所描述的正规语言；则,则 L(FA)的生成(或识别)过程如下所示：,如右图有限自动机：,3.2.2 有限自动机所描述的语言,,,即：,含义是:,,,,,,,,, L(FA)的生成(或识别)过程示例：,.第一条通路：FA1,,.第二条通路：FA2,,,,,,,, L(FA)=abnc, bn| n0 ,,因而,接受空串的 FA的典型特征！,,,【例3.6】有限自动机 ：FA=( Q,,S,F, ) 其中: Q=1,2,3,4,=a,b,c, S=1,2, F=3,4,FA 的两种表现形式：, 状态转换图:,3.2.3 有限自动机的两种表现形式, 变换表:, 变换表结构：行(状态)，列(符号)，表项(变换后状态),开始状态结束状态,,【例3.7】A= abnc,(ab)n|n0 ,3.2.4 有限自动机的分类,方法一：联合式,方法二：组合式1,方法三：组合式2,,,比较之：,的有限自动机构造：,,,,,,3.2.4 有限自动机的分类,【有限自动机分类】,1. 确定的有限自动机(DFA),特征：开始状态唯一; 变换函数单值; 不带边。

2. 非确定的有限自动机(NFA),(1) 带有边的非确定的有限自动机(NFA),(2) 不带有边的非确定的有限自动机( NFA),-- 不能全部满足上述特征者！,3.3 有限自动机的等价转换, 有限自动机的等价转换,主要包含两个内容：,,(1) 有限自动机的确定化( NFA=DFA);,,,ab* , b+ , ,L(FA2)=abn,bn|n0,,3.3.1 有限自动机的等价,. 两个自动机的等价：,FA2,FA1, L(FA1)=L(FA2), FA1FA2,四条通路，分别接受：,ab+ , ab* , b+ , ,L(FA1)=abn,bn|n0,二条通路，分别接受：,. 两个状态的等价：,3.3.1 有限自动机的等价,【例2】FA2,【例1】FA1:,24 ？,,35 ？,45 ？,判断等价性：,23 ？,, 2,3节点构成闭路 2,3等价；可合而为一,,,,,,(3) 对边，按通路逆向逐一进行：,3.3.2 有限自动机的确定化算法,. 消除 边算法( NFA = 或DFA ):,(1) 若存在闭路，则把闭路上各节点合而为一：,,(2) 标记隐含的开始态和结束态：,开始态的通路上的节点：+,结束态逆向通路上节点：-, 删除一个边；同时, 引进新边 ：,凡由原边终点发出的边，也要由其始点发出。

4) 重复步骤(3)，直到再无边为止2) 标记隐含的开始态和结束态：,,L(NFA)= ?, 消除边算法示例：,【例3.8】考查NFA：,(1) 闭路上的节点等价（ ）,可合而为一；,(3) 逆序逐一删除边，同时引进新边：,,,-,+,,,,,,+,+,+,3.3.2 有限自动机的确定化算法(续1),.把 化为DFA算法( =DFA ):,,(qi1,qin ,ak)= (qi1, ak) (qin, ak)=qj1,qjn,(3) 若qj1,qjn 未作为状态行标记，则作新行标记；,(4) 重复步骤(2)(3)，直到不再出现新状态集为止；,(5) 标记DFA的开始态和结束态：,第一行q01,q0n，(右侧)标记 + ；,凡是状态行中含有 的结束状态者，(右侧)标记 -,【注】必要时，新产生的DFA可用状态图表示字母表中符号,(1) 构造DFA的变换表(框架)：, ,, 确定化示例：,【例3.9】联合式自动机NFA:, 确定化过程:,DFA:,c,b,a,,D3,F2,E5,C2,4,,G4,,E5,D3,F2,,F2,,,E5,G4,,,,D3,D3,C2,4,,B2,5,,,B2,5,,,,,,,,,+,-,-,-,-,,,【注】A,B,C, 状态集的代码,,,,,A1,4,,,NFA确定化练习,1. 消除 边练习,2. 确定化练习,1. 消除 边练习的答案,2. 确定化练习的答案,NFA确定化练习,,3.3.3 有限自动机的最小化算法,,,最小有限自动机，是指满足下述条件的确定有限自动机：,(1) 没有无用状态(无用状态已删除)；(2) 没有等价状态(等价状态已合并)。

删除无用状态算法,【定义】无用状态是指自动机从开始态出发，对任何符号串都不能到达的状态判别算法】 构造有用状态集 Qus,,(1) 设 q0 为开始态，则 令 q0Qus ；,(2) 若 qiQus 且有 (qi,a)= qj 则令 qjQus ；,(3) 重复执行(2)，直到Qus不再增大为止4) 从状态集Q中，删除不在Qus中的所有状态3.3.3 有限自动机的最小化算法(续1),. 合并等价状态算法,【原理】两个状态i , j 等价，当且仅当满足下面两个条件：, 必须同是结束态，或同不是结束态；, 对所有字母表上符号，状态 i , j 必变换到等价状态例】把下述自动机最小化：,(1) 初分成两个不等价子集：,Q1=1,2,Q2=3,(2) 还能分成不等价子集吗？, (1,a)= 2 , (2,a)= 2 又 (1,b)= 3 , (2,b)= 3, 12(等价),合并后的最小自动机,,,3.3.3 有限自动机的最小化算法(续2),. 合并等价状态算法,(1) 初始，把状态集Q划分成两个不等价子集:,Q1(结束状态集)， Q2(非结束状态集)；,(2) 把每个Qi再划分成不同的子集，条件是：,,对同一Qi中两个状态 i 和 j ，若对字母表中的某个符号，变换到已划分的不同的状态集中，则 i 和 j 应分离:,(3) 重复步骤(2)，直到再不能划分为止；,(4) 合并最终划分的每个子集中的各状态(合而为一)。

如 (i,a)Qm , (j,a)Qn 且 mn,,--- 划分不等价状态集,, 有限自动机化简示例,,,【例3.10】 化简下述 DFA:,(1) 删除无用状态：,动态构造DFA变换表，即从开始状态 1 出发，,把变换后的状态填入表项，并同时作为新行标记；如此下去，直到再不出现新状态为止未出现的状态，就是无用的状态注】 DFA 中的状态 2，8 被删除!,,DFA的变换表：, 有限自动机化简示例(续1),(2) 合并等价状态:, 令 QNE= 1,3,4, 5,6,7 , 取 1,3,4 ：,即 QNE= 1,3,4, 5,6,7 , 取 3,4： (3,a)=1 ,(4,a)=4, 划分 Q1=3, Q2=4,即 QNE= 1,3,4, 5,6,7 , 取 5,6,7: 同理，可划分成 Q1=5, Q2=6,7；,,最后： QNE= 1,3,4, 5,6,7 ,不等价集,, 有限自动机化简示例(续2),,合并等价状态: 6 , 7,6替换7,最小的 DFA !,, 有限自动机化简练习,,,,删除无用状态,合并等价状态,,(3) 令 getchar(ch) 为读符号函数3.4 有限自动机的实现,用计算机完成有限自动机的功能，其核心是“变换”的实现技术。

这里介绍的是把变换表按某种方式存储起来，作为知识源来识别单词，实现机制是：,,【三点说明】,(1) 假定自动机只作为识别器，即对待识别的符号串：,仅回答 是(接受) 或 否(拒绝)2) 为便于处理，可令 # 作为待识别的符号串的后继符为此，扩展自动机如下：,,空则no,3.4.1 控制程序设计,开始状态1赋给变量 state,从输入串中读取一符号到变量 ch,变量 state 重新被赋值为变换后的状态！,,,3.4.2 变换表存储结构设计,变换表的存储结构可选择下述两种方式之一：,(1) 二维数组 ，其下标是(状态，输入符号)；, 为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整数：0,1,2,3,2) 压缩变换表，方法是把每个状态行作为子表，状态为索引，并把错误的输入符号合并在一起，如：,,,,索引表,(其他)--错误符号状态,变换子表,,, 有限自动机实现示例,【例3.11】 有限自动机DFA:,,,,压缩变换表,输入串 aacd# 识别过程：,索引。