图灵机

 内容：

 

练习：

1、关于“图灵机”，下列说法不正确的是_____。

A 图灵机给出的是计算机的理论模型,是一种离散的、有穷的、构造性的问题求解思路

B 图灵机的状态转移函数<q, X, Y, R(或L或N), p>，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，状态变为p

C 凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题任何算法也解决不了

D 上述有不正确的

2、下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

A 识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同

B 识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串

C 将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式

D 将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式

3、下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5，S6}，其中S1为起始状态，S6为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

A 识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同

B 识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串

C 将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式

D 将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式

解析：根据本题中&in, out, direction的描述及状态转移图，可以看到该图灵机是识别左侧连续0的个数和右侧连续1的个数相同的0、1串。首先来看S1、S2、S3的转移，一个串从S1开始，当遇到第一个0，将0转换成X，然后向右移一位，进入状态S2，该状态检测下一位是否为1，当不是的话，什么都不做，直接向右移一位，知道遇到第一个1，遇到以后，将1转换成Y，向左移动，进入到状态S3，该状态回溯0、1串，直到遇到X，然后指向在其右侧的符号，返回到S1状态。这个过程即为一个左侧连续0的个数和右侧连续1的个数相同的0、1串，每次都寻找排在最前面的一个0和一个1，将它们分别转换成X，Y，直到所有的0和1转换为X和Y。然后从状态S1到S5是右移到最右侧的字符，从右侧字符开始，将Y转换回1，将X转换回0，直到最左侧遇到空白字符，停止，此时的字符串已经还原回最初的字符串了。

4、下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空格”，；}；状态集合{S1，S2，S3，S4，S5，S6，S7}，其中S1为起始状态，S7为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

能够识别“V=C+C；”形式的符号串

能够识别“V=C；”形式的符号串

能够将符号串中的空格去除掉

上述全部能够识别

5、下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空格”，；}；状态集合{S1，S2，S3，S4，S5，S6，S7}，其中S1为起始状态，S7为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

关于该图灵机的功能，说法不正确的是_____。

既能够识别“V=C+C；”形式的符号串，又能识别“V=V+C；”形式的符号串

既能够识别“V=C；”形式的符号串，又能识别“V=V；”形式的符号串

既能够识别“V=V+C；”形式的符号串，又能识别“V=C+V；”形式的符号串

上述说法不正确，即有该图灵机不能识别的符号串形式
 

 

 

 

 

参考资料：

《大学计算机(第2版)—计算与信息素养》，战德臣，聂兰顺等著，高等教育出版社，第2版，2014.