文档介绍：学号姓名学院
……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………
电子科技大学研究生试卷
(考试时间: 至,共小时)
课程名称有限自动机理论教师陈文宇学时 40 学分 2
教学方式课堂面授考核日期年月日成绩
考核方式: (学生填写)
字母表为{a,b,c},构造下列语言的文法(10分)。
1) {x|x=xT, xÎå+};
2) {w|wÎå+,且w中a, b 的个数一样多}。
构造TM,计算n+m+k (10分)
三、构造识别下列语言的NFA。(15分)
{w|wÎ{0,1}+;且如果w以10结尾,则w的长度为偶数;如果w以1结尾,则w的长度为奇数}。
四、构造识别下列语言的DFA。(15分)
{x|xÎ{0,1}+ ;且x中最多只能含一个00子串}。
五、构造PDAM接受语言L={anb2man|n,m>=1}。(10分)
六、构造3道图灵机进行二进制数的加法运算。第1道存放第一个操作数,
第2道存放第二个操作数,第3道存放计算结果。(20分)
七、利用图灵机的子程序技术,构造Turing M,求非负整数的除法:n÷m。(25分)
定义:n÷m=0,当n=0, m≠0时;n÷m=1,当n=0, m=0时;
n÷m=∞,当n≠0,m=0时;n÷m=k,当n≠0,m≠0时(k取整数,如5÷3=1);
要求给出主程序的功能描述和子程序的状态转换函数。
子程序对应的格局转换为:
0i(5m-13)j1q10m=>*0i-m(5m-13)j+11qf0m
主程序功能: 1. 先检查n与m是否为0。当出现n=0时,向右查找m是否为0。若为0,则将1变为0,接收;当m!=0,将1变为B,将m个0全变为B,接收。2. 初始化状态q1,进入子程序。
当子程序结束,检查1左边剩余的0,如果有剩余的0,则状态转换为q1,否则整个任务结束,首先将1右边的符号变为B,然后依次扫描1左边的符号,将符号变为B,扫描到3就将1右面的B变为0。最后将1变为B。
子程序:向右扫描一个0,将令变为2;然后扫描1左边剩余的最右边0,将0变为5;返回忘做扫描1后面余下的0;每扫描一个0,就将1左边剩余的0中的最右边的变为5。当1右边的0扫描结束,将2变为0,状态变为qf。真个工作结束标志:当扫描1左边的0,并变为5时,扫描到|-,则结束,并将第一个3及前面的所有5变为B;
/*变换3的情况*/
<q1 , 0 , q2 , 2 , L > //扫描1右边第一个0
<q2 , 2 , q2 , 2 , L>
<q2 , 1 , q2 , 1 , L>
<q2 , 3 , q2 , 3 , L>
<q2 , 5 , q2 , 5 , L>
<q2 , 0 , q3 , 3 , R> //扫描到1左边第一个0,变为3
/*处理将1左边的0变换3时的情况,方法:将状态置为qf即可*/
<q2 , |- , q8 , |- , R> //扫描要变为3的1左边的0时,发现0扫描完
<q8 , 5 , q8 , 5 , R >
<q8 , 3 , q8, 3 , R>
<q8 , 1 , qf , 1 , R>
/*循