计算概论作业参考答案2012byhw01答案

1、计算概论作业参考解答助教：le2012 年 2 月作业一 2 月 22 日问题 1 请定义有穷状态转换系统，它读入任一 01 的序列并成功结束说明其字符集、初始状态和结束状态，画出转换图解 系统 = , , , 0, ，其中： = 0 ,= 0, 1, ( _)(0, ) (0, ) = (0, _), = 0, 1 = = 0 .状态转移图如下：(0, _)(1, _)start0注：字符串并没有任何格式限制，因此自表示，这是不必要的非常简单有的同学使用了两个甚至三个状态问题 2 请定义一个有穷状态转换系统，它读入 16 位长度的无符号二进制整数 ，输出二进制整数/2解 整数 /2 的二进制

2、形式就是将 去掉最后一位只输出前面的 15 位，读至最后一位不输出，成功结束即可1系统 = , , , 0, ，其中： = 0, 1, , 17 ,= 0, 1 , ( _)(, ) (, ) = (+1, ),(15, ) (15, ) = (16, _) = = 16 .0 14, = 0, 1注意这里的 只是部分函数，在 16 上无定义状态转换图如下：(0, 0)(1, 1)(0, 0)(1, 1)(0, 0)(1, 1)(0, _)(1, _)start012141516在这个解法中，严格遵循题目的要求：只输出 16 位整数除以 2 的结果，输入的字符串如果少于或多于 16 位，都会进

3、入非接受状态而出错在有限状态自还没有读完，则自中，如果转移函数（部分函数）在某个输入和状态下没有定义，而输入串不这个字符串，也就是机器出错有的同学在 16 处（或 15）又加上了无输出的自环，反而不对有的同学给出了一般的二进制串除以 2 的自字符，状态集和转移相对简单：(0, 0)，思路是在第 个位置输出第 1 位读入的(1, 1)(1, 0)start01(0, 1)这也是可以的因为并非系统学习有限自败的情形的专门理论，作业并不要求一定详细给出自失问题 3 考虑任意由 0, 1的序列 ，请定义一个图灵机 ，如果 形如 0.01.1，其中 0, 1的个数相同，则 关于 的计算结束，否则不结束能

4、设计一个有穷状态转移系统，使其对满足条件的输入成功结束吗？解 首先说明，要定义一个有穷状态转移系统识别形如0 0 1 1 , 1 的串，这是不可能的因为，有穷状态转移系统（或者说有限状态自）只能从左向右顺序读入文字，在 个符号 0 时，必须符号 0 的长度 ，然后才能判断后面跟随的 个符号 12是否数量合适有穷状态转换系统的外界输入只有顺序读入的符号串，不能以前写的内容，因此能数字的部分只有其状态由于系统的状态是有限的，但符号串的长度是（潜在）无限的，因而任何固定的有穷状态转移系统都不能保存足够长的数字 ，从而无法接受一般的符号串形式现说明 Turing 机的设计思路：Turing 机从左向右

5、扫描，每次改写纸带，改掉最左的一个 0 和最左的一个 1，然后回到原处，再次开始相同的流程到最后，所有的 0 和 1 都被改写的符号改写填满，就说明字符串匹配成功Turing 机的形式化表示与有限状态自类似，由状态集、输入符号表、带符号表、转移函数、初始状态、空格符号、接受状态七个部分组成： = , , , , 0, , = 0, 1, 2, 3, 4 , 0, 1, 0, 1, X, Y, B, , 0, B, 4其中转移函数 把状态与纸带读写头下符号如下表：到下一个状态、写下的符号和读写头移动方向01XYB状态(1, X, )(1, 0, )(2, 0, )(3, Y, )(1, Y, )

6、(2, Y, )(3, Y, )01234(2, Y, )(0, X, )(4, B, )状态转移图为：0/0, Y/Y, 10/X, 1/Y, 0/0, Y/Y, start02X/X, Y/Y, B/B, 34Y/Y, 注：本题可见自理论、语言和计算导论第三版，第八章自和图灵机理论在信息科学系有专门的课程“理论计算机科学基础”进行讲解这里的解答比较详细，但在计算概论课程中并不做详细的要求此题解法并不唯一，可以有多种思路因为过程比较繁琐，多数同学的作业我没有仔细检查，仅仅了一些明显的思路错误3问题 4 求出与下面二进制数对应的十进制数1010111110.1011011111110001010010解1010111(2) = 87(10)110.101(2) = 6.625(10)10111111(2) = 191(10)10001010010(2) = 1106(10)这里其实是纯数学的二进制记法在计算机中，并没有真正意义上的整数和实数的数据类型，整数