构造正规式相应的DFA.doc_第1页
构造正规式相应的DFA.doc_第2页
构造正规式相应的DFA.doc_第3页
全文预览已结束

下载本文档

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

文档简介

构造正规式相应的DFA：1(0|1)*101按照以下三步：（1）由正规表达式构造转换系统（NFA）（2）由转换系统（NFA）构造确定的有穷自动机DFA（3）DFA的最小化答：（1）首先构造与正规式1（0|1）*101相应的NFA，然后再将NFA确定化。为正规式构造NFA的方法为“语法制导”法，即依据正规式的语法构造来构造。首先将正规式r=1（0|1）*101分解成r=r1,r2r3，其中：r1=1，r2=（0|1）*，r3=101。对于r1，有：XA1对于r2，有：A0,1对于r3，有：XBCY110因此，与正规式r=r1r2r3相对应的NFA如图所示为：A0,1X1BCY110展开为：A30X1BCY110A2A11（2）将NFA转换成DFA采用子集法，即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C，假定C=T0，T1，Ti，集中T0=-closure（X），对于任何aTi=-closure（Move（Ti，a）。TiTi0Ti1A0 T0A1，A2，A3=T1A1，A2，A3 T1A2，A3=T2A2，A4，A3=T3A2，A3 T2A2，A3=T2A2，A4，A3=T3A2，A3，A4 T3A2，A5，A3=T4A2，A4，A3=T3A2，A3，A5 T4A2，A3=T2A2，A4，A6，A3=T6A2，A3，A4，A6 T5A2，A5，A3=T4A2，A4，A3=T3DFA的状态转换图T0T1T2T3T4T511111100000（3）化简DFA：分割法，把DFA的状态集分成一些不想交的子集，使得不同的两子集的状态是可区别的，同一子集的状态是等价的。首先，将状态分成两个子集：一个由终态组成，一个由非态组成：T0，T1，T2，T3，T4 T5 T0，T1，T2，T3 T4 T5 T0，T1，T2 T3 T4 T5 T0 T1，T2 T3 T4 T5在等价状态子集T1，T2中选状态T2做代表，消去其他状态T1，把从消去状态T1射出和
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

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

最新文档

评论

0/150

提交评论