形式语言与自动机课件图灵机

1SchoolofComputerScience&Technology,BUPT第五章图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。通过研究TM来研究递归可枚举集和部分递归函数为算法和可计算性研究提供了形式化描述工具。2SchoolofComputerScience&Technology,BUPT主要内容TM的基本定义TM的格局TM接受的语言TM的构造技术TM的变形；重点:TM的定义、TM的构造。难点:TM的构造。3SchoolofComputerScience&Technology,BUPTFinitecontrolX1BB...X2XnXi带（tape）单元格（cell）带符（tapesymbol）读写头在每一时刻扫描带上的一个单元带有一个最左单元，向右则是无限的。带的每个单元可容纳一个带符号开始时，最左边n个单元装着输入（n＝0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。图灵机的基本模型4SchoolofComputerScience&Technology,BUPT在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.将带头向左或者右移一个单元。*图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。图灵机的工作机制5SchoolofComputerScience&Technology,BUPT图灵机的形式化描述有限状态集有限输入符号集有限带符号集转移函数开始状态特殊带符:空白符终态集合q0QTB–TFQ转移函数:QQ{L,R}形式定义一个图灵机TM(Turingmachine)是一个七元组M=(Q,T,,,q0,B,F).6SchoolofComputerScience&Technology,BUPTδ函数示例：Q×∑→Q×∑×{L,R}δ(q,ai)=(p,B,L)q,p∈Qδ(q,ai)=(p,b,R)ai∈∑b∈∑格局用w1qw2描述图灵机的瞬间工作状态q为M的当前状态，w1w2∈∑*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：w1qw2表示读写头正扫描w2的最左字符w2＝则表示读写头正扫描一个空白字符。图灵机的函数与格局7SchoolofComputerScience&Technology,BUPT图灵机的格局给定图灵机M=(Q,T,,,q0,B,F)，定义格局之间的推导关系├M如下：1.设(q,Xi)=(p,Y,L)，则有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-2pXi-1Y…Xn，但有如下两个例外：（1）i=1时，qX1X2…Xn├MqYX2…Xn，和（2）i=n及Y=B时，X1X2…Xn-1qXn├MX1X2…Xn-2pXn-1B.2.设(q,Xi)=(p,Y,R)，则有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn，但有如下两个例外：（1）i=n时，X1X2…Xn-1qXn├MX1X2…Xn-1YpB，和（2）i=1及Y=B时，qX1X2…Xn├MBpX2…Xn-1Xn.8SchoolofComputerScience&Technology,BUPT图灵机接受的语言L(M)={ω│ω∈T*且q0ω├*α1pα2,p∈F,α1α2∈∑*}图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：当输入被接受时，图灵机将停止，没有下一个动作。9SchoolofComputerScience&Technology,BUPT任给图灵机M=(Q,T,,,q0,B,F)，以及输入字符串wT*.试问：对于w，M是否停机？停机是指图灵机不存在下一个移动步（move）.结论图灵机的停机问题是不可解的（即不可判定的）.结论任给图灵机M，很容易构造一个图灵机M，使得L(M)=L(M)，并满足：如果wL(M)，则对于w，M接受w并一定停机.如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机.但是，对不能接受的字符串，图灵机可能永不停止.（只要M还在某个输入上运行，我们无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）图灵机的停机问题10SchoolofComputerScience&Technology,BUPT图灵机举例例1：设语言L={anbn│n=1}，设计图灵机接受L。思路：最初带上为aa…abb…bBBB……n个an个b首先用x替换M最左边的a，再右移至最左边的b用y替换之，左移寻找最右的x，然后右移一单元到最左的a，重复循环。如果（1）当在搜寻b时，M找到了空白符B，则M停止，不接受该串。（此时，a的个数大于b的个数）（2）当将b改为y后，左边再也找不到a，此时,若右边再无b，接受；若仍有b，则b的个数大于a的个数，不接受。11SchoolofComputerScience&Technology,BUPT动作写的符号q0q1a/xa/a,y/yb/yy/yx/xa/a,y/yq3y/yq2B/Bq4RRRRL例1L={anbn│n=1}δ(q0,a)=(q1,x,R)δ(q0,y)=(q3,y,R)δ(q1,a)=(q1,a,R)δ(q1,y)=(q1,y,R)δ(q1,b)=(q2,y,L)δ(q2,a)=(q2,a,L)δ(q2,y)=(q2,y,L)δ(q2,x)=(q0,x,R)δ(q3,y)=(q3,y,R)δ(q3,B)=(q4,B,R)例：aabb的接收格局序列q0aabb├xq1abb├xaq1bb├xq2ayb├q2xayb├xq0ayb├xxq1yb├xxyq1b├xxq2yy├xq2xyy├xxq0yy├xxyq3y├xxyyq3B├xxyyq412SchoolofComputerScience&Technology,BUPTStartq6q1q00/Xq4Y/Y0/0Y/Y0/0X/XY/YB/BY/Yq31/Yq2Z/Z1/12/ZZ/Z1/1q5Z/ZZ/Z对于输入字符串001122，该图灵机可以有如下推导步：q0001122├MXq101122├MX0q11122├MX0Yq2122├MX0Y1q222├MX0Yq31Z2├*Mq3X0Y1Z2├MXq00Y1Z2├*MXXYYZq22├MXXYYq3ZZ├*MXq3XYYZZ├MXXq0YYZZ├*MXXYYq4ZZ├MXXYYZq5Z├MXXYYZZq5B├MXXYYZZBq6B例2L=0n1n2nn1.13SchoolofComputerScience&Technology,BUPT转移图与转移表Startq6q1q00/Xq4Y/Y0/0Y/Y0/0X/XY/YB/BY/Yq31/Yq2Z/Z1/12/ZZ/Z1/1q5Z/ZZ/ZStateq1q0q2q3q4(q1,X,R)(q1,0,R)(q2,Y,R)(q2,1,R)(q4,Y,R)(q1,Y,R)(q3,Y,L)Symbol01XYB(q2,Z,R)(q3,Z,L)Zq5q6(q6,B,R)(q3,0,L)(q3,1,L)(q0,X,R)(q4,Y,R)(q5,Z,R)(q5,Z,R)2(q3,Z,L)14SchoolofComputerScience&Technology,BUPT作为整数函数计算机的图灵机预备知识：图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。传统方法把整数表示成一进制整数i0用字符串0i表示如果一个函数有k个自变量，i1,i2,…ik，那么这些整数开始时被放在带上，并用1把他们分隔开。形如0i110i210i3…10ik如果图灵机停止(不论是否在一个接受状态上)且带上为0m，则f(i1,i2,…,ik)=mf是被图灵机计算的k元函数如果f（i1,i2…,ik）对所有i1,i2…,ik有定义,那么称f是一个全递归函数。全递归函数对应于递归语言，因为它总是被能停下来的图灵机所计算。所有常用的整数算术函数都是全递归函数。15SchoolofComputerScience&Technology,BUPT例3：设计图灵机求真减法思路：1.用空白符B代替带上的最左端的02．右移至紧跟1后的0,将其改为13．左移找到B，将B之后的0改为B4．重复上述过程如果（1）右移找0时，遇到B，意味着mnBB…B0m-(n+1)111…1n+1n个将后面n+1个1变为B，将左侧最后一个B变0，形如BB…B00m-(n+1)BB…Bn个n+1个这时，带上留下m-n个0，即结果为m-n0mnmnmnmn初始带0m10n16SchoolofComputerScience&Technology,BUPT求真减法（续）(2)M左移找不到0，意味着nm，形如BB…B111…10…0m个m个n-m个此时,用B替换所有剩余的1和00/0,1/1q3B/B0/11/1q00/01/10/Bq1q21/BB/Bq6q5q4B/BB/00/B,1/B0/0,1/BLRRRRRL17SchoolofComputerScience&Technology,BUPT例4：L=0mm=2n,n0设计思路：对输入串w1.从左到右扫描带，隔一个消一个0；2．若带上只剩唯一一个0,接受；3．若带上不止一个0,且个数为奇数，拒绝；4．让读写头返回带的最左端；5.转第一步。18SchoolofComputerScience&Technology,BUPTStartq4q2q10/#,RqrejectX/X,RB/B,Rq3B/B,Racceptqq5#/#,RB/B,LX/X,L0/0,L0/X,RX/X,RX/X,R0/X,R0/0,R识别L=0mm=2n,n0的图灵机19SchoolofComputerScience&Technology,BUPT课堂练习设计一个状态数不超过3的图灵机，它能够接受语言L=a(a+b)*，若假定T={a,b},两个状态的图灵机能否接受该语言？20SchoolofComputerScience&Technology,BUPT5.2图灵机的构造技术在设计图灵机的过程中，写出δ函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具。目的：设计时方便，但这些构造技术并未增加图灵机的功能。21SchoolofComputerScience&Technology,BUPT5.2.1.利用带存储区的状态（storageinthestate）此类图灵机M=(Q,,,,q0,B,F)中，状态中可以包含一个具有有限个取值的存储单元，即状态集合为Q=ST={[q,a]|qSaT}，其中qS通常表示控制状态，而aT通常表示数据元素.一般情况下，有限控制器内允许存储n个字符，即状态的第2个元素可存储n个字符。qabcStateStorageBX1BBB......X2XnXi22SchoolofComputerScience&Technology,BUPT例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视整个带，若找不到与第一个相同的字符，则M接受该字符串，否则不接受。构造M=(Q,{a,b},{a,b,B},δ,q0,B,F)其中Q={q0,q1}×{a,b,B}={[q0,a