有限自动机第三章答案.doc_第1页
有限自动机第三章答案.doc_第2页
有限自动机第三章答案.doc_第3页
有限自动机第三章答案.doc_第4页
有限自动机第三章答案.doc_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

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

文档简介

第三章*1构造下列语言的DFA ( 陶文婧 02282085 )（1）0，1*（2）0，1+ （3）x|x0，1+且x中不含00的串（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （4） x|x0，1*且x中不含00的串（可接受空字符串，所以初始状态也是接受状态）（5）x|x0，1+且x中含形如10110的子串（6）x|x0，1+且x中不含形如10110的子串（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）x|x0，1+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x0时，x的首字符为1 1. 以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2. 设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt3. 状态转移表为状态01q0q1q2q1q3q2q2q0q4q3q1q2q4q3q4 （8）x|x0，1+且x的第十个字符为1（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） （9）x|x0，1+且x以0开头以1结尾（设置陷阱状态，当第一个字符为1时，进入陷阱状态） （10）x|x0，1+且x中至少含有两个1 （11）x|x0，1+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数可将0，1+的字符串分为4个等价类。q0： e的等价类，对应的状态为终止状态q1:x的长度为奇且以0结尾的等价类q2：x的长度为奇且以1结尾的等价类q3: x的长度为偶且以0结尾的等价类q4: x的长度为偶且以1结尾的等价类（12）x|x是十进制非负数（13）F（14）e*2.*3.根据下列给定文法，构造相应的FA。 （敖雪峰 02282068）(1) 文法G1的产生式集合如下： G1: Sa|AaAa|Aa|cA|BbBa|b|c|aB|Bb|Cb(2) 文法G2的产生式集合如下： G2: Sa|Aa Aa|Aa|Ac|Bb
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论