NFA如何转换成等价的DFA

NFA如何转换成等价的DFA

ID:45330763

大小:1.16 MB

页数:13页

时间:2019-11-12

NFA如何转换成等价的DFA_第1页
NFA如何转换成等价的DFA_第2页
NFA如何转换成等价的DFA_第3页
NFA如何转换成等价的DFA_第4页
NFA如何转换成等价的DFA_第5页
资源描述:

《NFA如何转换成等价的DFA》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、主讲:陈小娟西南大学荣昌校区信息管理系NFA转换为等价的DFA4.3编译原理4.3.1基本概念(1)FA(finiteautomata)有穷自动机作为一种识别装置,它能准确地识别文法所定义的语言和正规式表示的集合。引入FA的目的:是为词法分析程序的自动构造寻找方法和工具。NFADFAFA(2)DFA(deterministicfiniteautomata)确定的有穷自动机(3)NFA(nondeterministicfiniteautomata)不确定的有穷自动机两者的区别是:转换函数和初态方面的不同4.3.1基本概念(1)定理:设L为一个由不

2、确定的有穷自动机接受的集合,则存在一个接受L的确定的有穷自动机。(2)子集法:将不确定的有穷自动机转换成接受同样语言的确定的有穷自动机。4.3.2NFA转换为等价的DFA的算法定义对状态集合I的几个有关运算:1状态集合I的-闭包,表示为-closure(I),定义为一状态集,是状态集I中的任何状态S经任意条弧而能到达的状态的集合。I={1},-closure(I)={1,2};12534aaa例687I={5},-closure(I)={5,6,2};4.3.2NFA转换为等价的DFA的算法2状态集合I的a弧转换,表示为mo

3、ve(I,a)定义为状态集合J,其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。定义Ia=-closure(J)move({1,2},a)={5,3,4}-closure({5,3,4})=Ia={2,3,4,5,6,7,8}12534aaa例6874.3.2NFA转换为等价的DFA的算法构造NFAN的状态K的子集的算法算法描述如下:假定所构造的子集族为C,即C=(T1,T2,...TI),其中T1,T2,...TI为状态K的子集。1.开始,令-closure(K0)为C中唯一成员,并且它是未被标记的。构造NFA

4、N的状态K的子集的算法:2. while(C中存在尚未被标记的子集T)do{标记T;for每个输入字母ado{U:=-closure(move(T,a));ifU不在C中then将U作为未标记的子集加在C中} }例将下图的NFAN转换成DFAM023456789101εεεεεεεεbbbaaNFAN图4.3.3应用举例023456789101εεεεεεεεbbbaaIaIbT0=-closure(0) ={0,1,2,4,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}T1={1,2,3,4,6,7,8}{1,2,3,4,6

5、,7,8}{1,2,4,5,6,7,9}T2={1,2,4,5,6,7}{1,2,3,4,6,7,8}{1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T4={1,2,4,5,7,10}{1,2,3,4,6,7,8}{1,2,4,5,7,10}{1,2,3,4,6,7,8}{1,2,4,5,6,7}IaIb012113212314412b02134abaaaabbbP72第3题NFA转换为等价的DFAexerciseThankyou!

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。