非确定的有限状态自动机non-deterministicfiniteautomaton-

上传人:suns****4568 文档编号:96130784 上传时间:2019-08-24 格式:PPT 页数:48 大小:622.50KB
返回 下载 相关 举报
非确定的有限状态自动机non-deterministicfiniteautomaton-_第1页
第1页 / 共48页
非确定的有限状态自动机non-deterministicfiniteautomaton-_第2页
第2页 / 共48页
非确定的有限状态自动机non-deterministicfiniteautomaton-_第3页
第3页 / 共48页
非确定的有限状态自动机non-deterministicfiniteautomaton-_第4页
第4页 / 共48页
非确定的有限状态自动机non-deterministicfiniteautomaton-_第5页
第5页 / 共48页
点击查看更多>>
资源描述

《非确定的有限状态自动机non-deterministicfiniteautomaton-》由会员分享,可在线阅读,更多相关《非确定的有限状态自动机non-deterministicfiniteautomaton-(48页珍藏版)》请在金锄头文库上搜索。

1、非确定的有限状态自动机 Non-deterministic Finite Automaton, NFA,付国宏 黑龙江大学计算机科学技术学院 ,第三章 有限状态自动机,2019/8/24,2,引言,FA的修改 DFA对于同一个输入,从同一个状态出发只能有一个转移; 能否修改FA,使它对同一个输入从同一个状态出发可以有零个、一个或多个转移; 从而得到一个更为紧凑(状态数量较少)、更为容易设计的自动机 非确定有穷状态自动机 (non-deterministic finite automaton, NFA),2019/8/24,3,提要,主要内容 NFA 非形式化描述、形式定义、NFA与DFA的等价

2、性; -NFA 形式定义、 -NFA与NFA的等价性 重点 NFA和-NFA的概念、DFA和NFA以及-NFA和NFA之间的等价转换方法; 难点 对NFA和-NFA概念的理解;NFA与DFA的等价性证明;,2019/8/24,4,提要,主要内容 NFA 非形式化描述、形式定义、NFA与DFA的等价性; -NFA 形式定义、 -NFA与NFA的等价性 重点 NFA和-NFA的概念、DFA和NFA以及-NFA和NFA之间的等价转换方法; 难点 对NFA和-NFA概念的理解;NFA与DFA的等价性证明;,NFA,非形式描述 形式定义 扩展转移函数 从NFA构造DFA NFA与DFA的等价性,2019

3、/8/24,6,NFA的非形式化描述,NFA对同一个输入符号,从一个状态出发可以有零个、一个或多个转移。,L(M1)=x|x为01结尾的0和1的串,L(M1)=x|x为以0开始、1结尾的0和1的串,2019/8/24,7,NFA的非形式化描述 (cont.),NFA与DFA的区别 并不是对于所有的(q,a)Q,(q,a)都有一个状态与它对应; 并不是对于所有的(q,a) Q,(q,a)只对应一个状态; NFA在任意时刻可以处于有穷多个状态; NFA具有“智能” 具备同时处理多个状态的能力; 具备对输入进行预测的能力;,2019/8/24,8,NFA的非形式化描述 (cont.),例:M1如何接

4、受00101,q0,q0,q0,q0,q0,q0,q1,q1,q1,q2,q2,不能继续,不能继续,2019/8/24,9,NFA的形式定义,非确定的有穷状态自动机(Non-deterministic finite automaton, NFA) 五元组: M=(Q, , , q0, F),有穷状态集,输入字母表,状态转移函数,开始状态q0Q,终止状态集FQ,: Q2Q,(q, a)Q,(q, a)= p1,p2,pm,M在状态q读入字符a,可以选择地将状态变成p1,p2,或pm ;,将读头向右移动一个带方格而指向输入字符串的下一个字符;,2019/8/24,10,NFA的表示,接受x|x0,

5、1*,且x含有子串00或11的NFA的表示,状态转移表,状态转移图,M=(q0, q1, q2, q3, 0, 1, , q0, q0 , q3) (q0, 0)=q0, q2, (q0, 1)=q0, q2, (q1, 0)=q3, (q1, 1)=, (q2, 0)=, (q2, 1)=q3, (q3, 0)=q3, (q3, 1)=q3,四元组,2019/8/24,11,把状态函数扩展到串,设NFA M=(Q, , , q0, F) : Q2Q 扩展定义 : Q*2Q 的递归定义 (1) 基础:qQ, (q, )=q; (2) 归纳:设串x形如wa (w*,a),qQ, (q, w)=p

6、1,p2, , pk,则 (q, wa)= p|r(q, w), 使得p(r, a) 可以不区分 (q, a)和 (q, a) (q, a)= (q, a),2019/8/24,12,把状态函数扩展到串 (cont.),设x=a1a2an * ,则 (q, x)的计算如下: 举例:用描述右图所示 的NFA处理01100的过程,1. (q0, )=q0,2. (q0, 0)=(q0, 0)=q0, q1,3. (q0, 01)=(q0, 1)(q1, 1)=q0, q2=q0, q2,4. (q0, 011)=(q0, 1)(q2, 1)=q0, q2q3=q0, q2, q3,5. (q0,

7、0110)=(q0, 0)(q2, 0)(q3, 0) =q0, q1q3=q0, q1, q3,6. (q0, 01100)=(q0, 0)(q1, 0)(q3, 0)=q0, q1q3q3=q0, q1, q3,2019/8/24,13,NFA接受的语言,NFA接受(识别)的字符串 x*, 如果(q0,x) F,则称x被M接受; 如果(q0,x)F=,则称M不接受x ; NFA接受(识别)的语言 L(M)=x| x*且(q0,x)F,2019/8/24,14,NFA与DFA的比较,DFA vs. NFA,都是正则语言的识别模型;,从定义角度,对于一个输入字符,,NFA可以进入若干个状态;,

8、DFA只能进入一个惟一的状态;,从DFA看待问题的角度来说,,NFA在某一时刻同时进入若干个状态,但是,这若干个状态合在一起的“总效果”相当于它处于一个“综合状态”;,可让DFA用一个状态去对应NFA的一组状态。,DFA可看作是一种特殊的NFA;,2019/8/24,15,NFA与DFA的对应关系,NFA MN=(Q, , N, q0, FN)与DFA MD=(Q2, , D, q0, FD)的对应关系 NFA从开始状态q0启动,相应的DFA则从状态q0启动,所以q0=q0; 对于NFA 的一个状态组q1,q2,qn 如果NFA在此状态组时读入字符a后可以进入状态组p1, p2,pm, 则让相

9、应的DFA在状态q1,q2,qn读入字符a时,进入状态p1,p2,pm;,DFA能做NFA所做的一切!,为了区分,用表示DFA上的状态集合,2019/8/24,16,从NFA构造等价的DFA,设NFA MN=(QN, , N, q0, FN),构造DFA MD=(QD, , D, q0, FD),使得L(MN)=L(MD) 方法一:子集构造法 MN和MD具有相同的字母表; MD的初始状态是只包含MN初始状态的集合,为区别记作q0; QD是QN的幂集,即 ; FD是所有至少含有一个MN的接受状态的MN的状态集合的集合,即:FD=S|SFN且S QN; S QN和a, 为了计算D,需要检查S中的所

10、有状态p,看看MN在输入a时从p进入那些状态,这些状态的并集即D.,2019/8/24,17,从NFA构造等价的DFA (cont.),例 3-7 构造下图所示的NFA 对应的DFA,NFA状态转移图,NFA状态转移表,2019/8/24,18,从NFA构造等价的DFA (cont.),针对QN所有子集S和所有输入符号计算D(S, a),2019/8/24,19,从NFA构造等价的DFA (cont.),不可达状态(inaccessible state),如果存在从q0对应的顶点出发,到达某个状态对应的顶点的路,,则称该状态从开始状态是可达的;,否则,就称该状态从开始状态是不可达的;,2019

11、/8/24,20,从NFA构造等价的DFA (cont.),确定可达状态,2019/8/24,21,从NFA构造等价的DFA (cont.),绘制DFA状态转移图 不可达的状态是无用的或无意义的,可以去掉,q0,q1,q0,q1,q3,1,1,0,0,S,q0,1,0,q0,q2,q0,q2,q3,0,1,0,1,1,2019/8/24,22,从NFA构造等价的DFA (cont.),小结:子集构造法主要步骤 (1) 根据给定NFA MN,构造其状态集合的所有子集,即幂集 ; (2) ,计算 (3) 从q0依次判断S是否可达状态; (4) 去掉所有不可达状态,剩下的状态及其相应的转移就构成DF

12、A的状态转移表。,2019/8/24,23,从NFA构造等价的DFA (cont.),方法二:画图法 先画出开始状态q0的图; 如果图中有未处理的顶点 任选一个未处理的状态q1,q2,qn; 对中的每个字符a,计算(q1,q2,qn,a); 如果(q1,q2,qn,a)已经是图的一个顶点, 则在图中画一条从顶点q1,q2,qn到顶点(q1,q2,qn,a)标记为a的弧; 如果(q1,q2,qn,a)不是图的一个顶点, 则在图中增加一个标记为(q1,q2,qn,a)的顶点,并画一条从顶点q1,q2,qn到顶点(q1,q2,qn,a)标记为a的弧; 如此重复下去,直到图中不存在未处理的顶点。,20

13、19/8/24,24,从NFA构造等价的DFA (cont.),q0,q1,1,0,S,q0,q0,q2,(3) 考察状态 q0, q1关于0和1的转移,q0,q1,q3,0,1,(4) 考察状态 q0, q2关于0和1的转移,0,1,q0,q2,q3,(5) 考察状态 q0, q1, q3关于0和1的转移,0,1,(6) 考察状态 q0, q2, q3关于0和1的转移,0,1,例:用绘图法构造例3-7所示的NFA 对应的DFA,(2) 考察状态 q0关于0和1的转移,(1) 先画出开始状态 q0,2019/8/24,25,NFA与DFA等价,定理 3-1 NFA与DFA等价 证明 (1)构造

14、与NFA M1等价的DFA M2 设M1=(Q1,1,q0,F1), 构造M2=(Q2, , 2, q0, F2) Q2=2Q F2=p1,p2,pm|p1,p2,pmQ1且p1,p2,pmF1 2(q1,q2,qn,a)=p1,p2,pm 1(q1,q2,qn,a)= p1,p2,pm,2019/8/24,26,NFA与DFA等价(cont.),(2)x*,施归纳于|x|证明:1(q0,x)= p1,p2,pm 2(q0,x)= p1,p2,pm 当|x|=0时,x= 1(q0,)= q0, 2(q0, )=q0, 结论成立; 设当|x|=n时结论成立,往证当|x|=n+1时结论也成立 不妨设x=wa,|w|=n,a 1(q0, wa)=1(1(q0, w), a) =1(q1, q2, , qn, a) =p1, p2, , pm 由归纳假设 1(q0,w)=q1,q2,qn 2(q0,w)=q1,q2,qn,2019/8/24,27,NFA与DFA等价(cont.),根据2的定义 2(q1, q2, , qn, a)=p1, p2, , pm 1(q1, q2, , qn, a)=p1, p2, , pm; 于是, 2(q0,wa)= 2(2(q0,w),a)

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 大杂烩/其它

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号