NFA如何转换成等价的DFA_第1页
NFA如何转换成等价的DFA_第2页
NFA如何转换成等价的DFA_第3页
NFA如何转换成等价的DFA_第4页
NFA如何转换成等价的DFA_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

NFA转换为等价的DFA

4.3编译原理14.3.1基本概念(1)

FA（finiteautomata）有穷自动机作为一种识别装置，它能准确地识别文法所定义的语言和正规式表示的集合。

引入FA的目的：是为词法分析程序的自动构造寻找方法和工具。

NFADFAFA2(2)DFA(deterministicfiniteautomata)确定的有穷自动机(3)NFA（nondeterministicfiniteautomata）不确定的有穷自动机两者的区别是：转换函数和初态方面的不同4.3.1基本概念3(1)定理:设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。(2)子集法：将不确定的有穷自动机转换成接受同样语言的确定的有穷自动机。4.3.2NFA转换为等价的DFA的算法4定义对状态集合I的几个有关运算：1状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。

I={1},-closure(I)={1,2}；12534aaa例687I={5},-closure(I)={5,6,2}；4.3.2NFA转换为等价的DFA的算法52状态集合I的a弧转换，表示为move(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}12534aaa例6874.3.2NFA转换为等价的DFA的算法6构造NFAN的状态K的子集的算法算法描述如下：假定所构造的子集族为C，即C=(T1,T2,...

TI),其中T1,T2,...

TI为状态K的子集。1.开始，令-closure(K0)为C中唯一成员，

并且它是未被标记的。7构造NFAN的状态K的子集的算法：2.

while（C中存在尚未被标记的子集T）do {标记T；

for每个输入字母ado {U:=-closure(move(T,a))；

ifU不在C中then

将U作为未标记的子集加在C中

}

}8例

将下图的NFAN转换成DFAM023456789101εεεεεεεεbbbaaNFAN图4.3.3应用举例9023456789101εεεεεεεε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,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}10IaIb0121132123144

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论