文档介绍：学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………电子科技大学研究生试卷(考试时间:至,共小时)课程名称有限自动机理论教师陈文宇学时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分)七、利用图灵机的子程序技术,构造TuringM,求非负整数的除法: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(5n-13)j1q10n=>*0i-m(5n-13)j+11qf0n