2012-2013-1《有限自动机理论》.doc_第1页
2012-2013-1《有限自动机理论》.doc_第2页
2012-2013-1《有限自动机理论》.doc_第3页
2012-2013-1《有限自动机理论》.doc_第4页
全文预览已结束

下载本文档

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

文档简介

学 号 姓 名 学 院 密封线以内答题无效 电子科技大学研究生试卷 （考试时间： 至 ，共2小时） 课程名称 有限自动机理论 教师 陈文宇 学时 40 学分 2 教学方式 课堂面授 考核日期 2012 年 5 月 21 日 成绩 考核方式： （学生填写）一、 分别构造产生下列语言的文法（15分）。1) w|wa，b，c，d+，且w中a, b, d的个数一样多。（7分）（7分）2) w|wa,b +，且w最多有一个aaa子串或者最少有一个bb子串（8分）二、La,b*1a,b,c+，试构造满足要求的文法G产生该语言(10分)。1) G是RG。 3）G是CSG，但不是CFG。2) G是CFG，但不是RG。 4）G是PSG，但不是CSG。三、构造接收下列语言的DFA。（15分）w|w0,1+，且w中最多只能含二个011子串四、构造接收下列语言的NFA。（15分）w|w0,1*；且若w以111结尾，则w的长度必须为奇数；若w以0结尾，则w的长度必须为偶数w|w0,1+；且w必须包含00子串w|w0,1+；且w不包含11子串五、构造PDAM接受语言L=anbm|0=n=m（10分）六、构造3道Turing M进行非负二进制数的3种关系运算（=、）。第1道存放第一个操作数，第2道存放第二个操作数（假设两个数不以0开头，已经是左对齐，读/写头在数的最高位），第3道存放结果（第3道为0：表示相等；第3道为00：表示小于；第3道为000：表示大于）。（15分）利用二道图灵机来实现图灵计数器，可以计数输入带上符号个数。第一道存放待记数的字符串；第二道存放记数的结果（十进制，初始为0）。构造2道Turing M进行非负二进制数的关系运算（结论为：大于、小于或等于）。第1道存放第一个操作数，第2道存放第二个操作数。（15分）（假设每个数最多16位，两个数已经是右对齐，高位非数字位以B表示，并且读/写头已经在最后，即数的最低位）七、利用图灵机的子程序技术，构造3道Turing M，进行非负整数的除法运算mn。第1道存放第一个操作数，第2道存放第二个操作数。第3道存放结果。子程序完成一次减法运算：将第一道的n个0删除，在第三道的末尾增加一个0。子程序开始，读写头位置如图1所示；以状态start_sub为开始状态，以状态end_sub为结束状态。请简略描述主程序的算法；给出子程序的指令（20分）B.B0.0B.0.0B.0.B.利用图灵机的子程序技术，构造3道Turing M，进行非负整数的乘法运算mn。第1道存放第一个操作数m，第2道存放第二个操作数n，第3道存放结果。子程序完成一次加法运算：在第三道的末尾增加n个0。子程序开始，读写头位置如图1所示；以状态start_sub为开始状态，以
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论