当前位置：文档库 › 研究生《有限自动机理论》往届试卷

研究生《有限自动机理论》往届试卷

1 电子科技大学研究生试卷（考试时间：至，共小时）课程名称有限自动机理论教师陈文宇学时 40 学分

2 教学方式课堂面授考核日期年月日成绩考核方式：（学生填写）

一、字母表为{a ，b ，c}，构造下列语言的文法（10分）。 1) {x|x=x T , 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={a n b2m a n|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+11q f0m

●主程序功能：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，状态变为q f。真个工作结束标志：当扫描1

2010有限自动机真题（回忆版）

1写文法：

1）{a，b，c}+上的语言，倒数第二个字母在前面至少出现一次

2）{a，b，c，d}*上的语言，字母出现相同次数

2 {0{0，1}*1}分别按四种类型写文法

3 DFA：{0，1}上的语言最多出现两次01

4 NFA：{0，1}上的语言,以1结尾，长度为奇，以00结尾长度为偶

5 PDAM，接收{b n a2m a3n，n>=0;m>0}

6多道图灵机实现二进制减法

7子程序：除法，说明主程序的功能，写出子程序状态转移函数。

要求子程序状态转移式为0i（6m-15）j1 q10m=>*0i-m（6m-15）j+11 q f0m