- 1、本文档共49页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
∑*上的符号串t被NFA M接受也可以这样理解:对于Σ﹡中的任何一个串t,若存在一条从某一初态结到某一终态结的道路,且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t,则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结,或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为ε,那么空字可为M所接受。 3.4.3 NFA转换为等价的DFA 对每个NFA N一定存在一个DFA M ,使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 基本思路(子集法) DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态. 定义对状态集合I的几个有关运算:1. 状态集合I的ε-闭包,表示为ε-closure(I),定义为一状态集,是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。2. 状态集合I的a弧转换,表示为move(I,a)定义为状态集合J,其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。 例 ?-closure(0)={0,1,2,4,7} move({0,1,2,4,7},a)={3,8} ?-closure({3,8})={1,2,3,4,6,7,8} NFA确定化算法假设NFA N=(K, ?,f,K0,Kt)按如下办法构造一个DFA M=(S, ?,d,S0,St),使得L(M)=L(N):1. M的状态集S由K的一些子集组成。用[S1, S2,... ,Sj]表示S的元素,其中S1, S2,... , Sj是K的状态。并且约定,状态S1, S2,... ,Sj是按某种规则排列的,即对于子集{S1, S2}={ S2, S1,}来说,S的状态就是[S1 S2];2. M和N的输入字母表是相同的,即是?;3. 转换函数是这样定义的:d([S1, S2,... ,Sj],a)= [R1,R2,... ,Rt],其中[R1,R2,... , Rt]=?-closure(move({S1, S2,…, Sj},a)) 4. S0=?-closure(K0)为M的开始状态;5. St={[Si, Sk,…, Se],其中[Si, Sk,... ,Se]?S且{Si , Sk,... , Se}?Kt??} 构造NFA N的状态K的子集的算法假定所构造的子集族为C,即C= (T1, T2,... , TI),其中T1, T2,... , TI为状态K的子集。1. 开始,令?-closure(K0)为C中唯一成员,并且它是未被标记的。2. while (C中存在尚未被标记的子集T) do { 标记T; for 每个输入字母a do { U:= ?-closure(move(T,a)); if U不在C中 then 将U作为未标记的子集加在C中 } } 3.4.4 确定有穷自动机的化简 对于任一个DFA,存在一个唯一的状态最少的等价的DFA。 一个有穷自动机是化简了的,即是说它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态是指是指这样的状态:从该自动机的开始状态出发,任何输入串也不能到达那个状态。 0 1 s0 s1 s2 s3 s5 s7 s1 s5 s1 s2 s2 s5 s5 s1 s1 s3 s0 s1 0 1 s0 s1 s2 s3 s4 s5 s6 s7 s8 s1 s5 s7 s2 s2 s5 s5 s7 s5 s6 s1 s3 s8 s0 s0 s1 s3 s6 例: 画状态图可以看出s4,s6,s8为不可达状态应该消除 状态s和t的等价条件是: 一致性条件:状态s和t必须同时为可接受状态或不接受状态。 蔓延性条件:对于所有输入符号,状态s和t必须转换到等价的状态里。 有穷自动机的状态s和t不等价,称这两个状态是可区别的。 DFA的最小化算法- “分割法” 把一个DFA的状态分成一些不相交的子集,使得任何不同的两子集的状态都是可区别的,而同一子集中的任何两个状态都是等价的。 3.5正规式和有穷自动机的等价性 有穷自动机和正规表达式的等价性:1.对于∑上的一个NFA M,可以构造一个∑上的正规式R,使得L(R)=L
您可能关注的文档
- 第5章Word2003文字处理.ppt
- 第3章__自动机基础.ppt
- 第3章_4逻辑移位及串操作.ppt
- 第5章xjs现代通信案例.ppt
- 第5章安山岩-花岗岩成因.ppt
- 第一章--糖类.ppt
- 第3章_CATIA_V5_草图设计.ppt
- 第5章半导体激光器(LD):静态特性_蓝色(全).ppt
- 第5章薄膜应用-2.ppt
- 第5章变速器设计.ppt
- 人教版九年级英语全一册单元速记•巧练Unit13【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit9【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit11【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit14【单元测试·提升卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit8【速记清单】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit4【单元测试·提升卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit13【单元测试·基础卷】(原卷版+解析).docx
- 人教版九年级英语全一册单元速记•巧练Unit7【速记清单】(原卷版+解析).docx
- 苏教版五年级上册数学分层作业设计 2.2 三角形的面积(附答案).docx
- 人教版九年级英语全一册单元速记•巧练Unit12【单元测试·基础卷】(原卷版+解析).docx
最近下载
- 2024年中国石油秋季招聘通用能力考试笔试备考试题及答案解析.docx
- 第一课 教室盆栽我做主—盆栽养护 课件 浙科版综合实践活动四年级上册.pptx
- 医疗安全(不良)事件根本原因分析法活动指南.pdf VIP
- 2023年中考押题预测卷02(杭州卷)-英语(考试版)A4.docx
- 于品 清华丘班数学分析讲义.pdf VIP
- 金融风险管理(中央财经大学)中国大学MOOC(慕课)章节测验试题(答案).pdf
- 一年一度喜剧大赛江东鸣《先生请出山》完整台词.docx VIP
- 党员立足本职岗位发挥党员先锋引领作用发言稿.doc VIP
- 《机床电气控制》M7130型卧轴矩台平面磨床的电气控制.pdf VIP
- Unit 4 Period 4 Developing Ideas 课件-高一上学期英语课件(外研社2019必修第一册).pptx
文档评论(0)