形式语言自动机——图灵机(一).ppt
1School of Computer Science&Technology,BUPT第五章第五章 图灵机图灵机A.Turing在1936年 介绍了这样一个通用的计算模型，该模型具有以下两个性质n该模型的每个过程都是有穷可描述的；n过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。n通过研究TM来研究递归可枚举集和部分递归函数n为算法和可计算性研究提供了形式化描述工具。2School of Computer Science&Technology,BUPT主要内容主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点:TM的定义、TM的构造。n难点:TM的构造。3School of Computer Science&Technology,BUPTFinitecontrolX1BB.X2XnXi带（带（tape）单元格（单元格（cell）带符（带符（tape symbol）n 读写头在每一时刻扫描带上的一个单元读写头在每一时刻扫描带上的一个单元n 带有一个最左单元，向右则是无限的。带有一个最左单元，向右则是无限的。n 带的每个单元可容纳一个带符号带的每个单元可容纳一个带符号开始时，最左边开始时，最左边n个单元装着输入（个单元装着输入（n0，n为有限数），它是为有限数），它是一个字符串，符号都选自一个字符串，符号都选自“带符号带符号”的一个子集，即所谓的的一个子集，即所谓的“输输入符号集合入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但的带符号，但不是不是输入符号。输入符号。图灵机的基本模型4School of Computer Science&Technology,BUPT在在一一个个图灵灵机机的的动作作中中，图灵灵机机根根据据带头（读写写头）所）所扫描的符号和有限控制器的状描的符号和有限控制器的状态可能作可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.n将带头向左或者右移一个单元。*图灵灵机机和和双双向向有有限限自自动机机的的区区别：图灵灵机机能能改改变它它带上的符号。上的符号。图灵机的工作机制5School of Computer Science&Technology,BUPT图灵机的形式化描述图灵机的形式化描述 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数转移函数 :Q Q L,R 形式定义形式定义 一个图灵机一个图灵机 TM(Turing machine)是一个七元组是一个七元组 M=(Q,T,q0,B,F).6School of Computer Science&Technology,BUPTn函数示例：函数示例：Q Q Q QL,RL,R(q,a(q,ai i)=(p,B,L)q,p Q)=(p,B,L)q,p Q (q,a (q,ai i)=(p,b,R)a)=(p,b,R)ai i b b n格局格局用w1q w2描述图灵机的瞬间工作状态q为M的当前状态，w1w2*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：定：w w1 1q wq w2 2表示表示读写写头正正扫描描w w2 2的最左字符的最左字符w w2 2 则则表示表示读读写写头头正正扫扫描一个空白字符。描一个空白字符。图灵机的函数与格局7School of Computer Science&Technology,BUPT图灵机的格局图灵机的格局 给定图灵机给定图灵机 M=(Q,T,q0,B,F)，定义格局之间定义格局之间的推导关系的推导关系M 如下：如下：1.设设 (q,Xi)=(p,Y,L)，则有则有 X1X2Xi-1qXiXi+1Xn M X1X2Xi-2pXi-1YXn，但有如下两个例外但有如下两个例外：（1）i=1时，时，qX1X2Xn M qYX2Xn，和和 （2）i=n及及 Y=B 时，时，X1X2Xn-1qXn M X1X2Xn-2pXn-1 B.2.设设 (q,Xi)=(p,Y,R)，则有则有 X1X2Xi-1 q XiXi+1Xn M X1X2Xi-1Y p Xi+1Xn，但有如下两个例外但有如下两个例外：（1）i=n时，时，X1X2Xn-1q Xn M X1X2Xn-1Y p B，和和 （2）i=1及及 Y=B 时，时，q X1X2XnM B p X2Xn-1Xn.8School of Computer Science&Technology,BUPT图灵机接受的语言图灵机接受的语言L(M)=TT*且且q q0 0*1 1 p p 2 2 ,pF,pF,1 12 2*图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：假定：当输入被接受时，图灵机将停止，没有下一个动作。9School of Computer Science&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还在某个输入上运行，我们无法知道是因为运行的时间不还在某个输入上运行，我们无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）够长而没有被接受，还是根本就不会停机）图灵机的停机问题图灵机的停机问题 10School of Computer Science&Technology,BUPT图灵机举例图灵机举例例例1 1：设语言：设语言 L=aL=an n b bn nn=1n=1，设计图灵机接受设计图灵机接受L L。思路：最初带上为思路：最初带上为 a aa a a b ba b b b B B B b B B B n n个个a na n个个b b首先用首先用x x替换替换M M最左边的最左边的a a，再右移至最左边的再右移至最左边的b b用用y y替换之，左移替换之，左移寻找最右的寻找最右的x x，然后右移一单元到最左的然后右移一单元到最左的a a，重复循环。重复循环。如果如果（1 1）当在搜寻）当在搜寻b b时，时，M M找到了空白符找到了空白符B B，则则M M停止，不接受该串。停止，不接受该串。（此时，（此时，a a的个数大于的个数大于b b的个数）的个数）（2 2）当将当将b b改为改为y y后，左边再也找不到后，左边再也找不到a a，此时此时,若右边再无若右边再无b b，接受；若仍有接受；若仍有b b，则则b b的个数大于的个数大于a a的个数，不接受。的个数，不接受。11School of Computer Science&Technology,BUPT例例1 L=an bnn=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)例：例：aabbaabb的接收格局序列的接收格局序列q q0 0aabb xqaabb xq1 1abb xaqabb xaq1 1bb xqbb xq2 2ayb qayb q2 2xaybxqxaybxq0 0aybxxqaybxxq1 1ybyb xxyq xxyq1 1bxxqbxxq2 2yyxqyyxq2 2xyyxxqxyyxxq0 0yyxxyqyyxxyq3 3yxxyyqyxxyyq3 3BxxyyqBxxyyq4 4 12School of Computer Science&Technology,BUPT对于输入字符串对于输入字符串001122，该图灵机可以有如下推导该图灵机可以有如下推导步：步：q0001122MXq101122 MX0q11122MX0Yq2122MX0Y1q222MX0Yq31Z2*Mq3X0Y1Z2MXq00Y1Z2*MXXYYZq22MXXYYq3ZZ*MXq3XYYZZMXXq0YYZZ*MXXYYq4ZZMXXYYZq5ZMXXYYZZq5BMXXYYZZBq6B例例2 L=0n1n2n n 1.13School of Computer Science&Technology,BUPT 转移图与转移表转移图与转移表14School of Computer Science&Technology,BUPT 作为整数函数计算机的图灵机作为整数函数计算机的图灵机n预备知知识：图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。n传统方法把整数表示成一方法把整数表示成一进制制整数 i 0 用字符串 0i 表示n如果一个函数有k个自变量，i1,i2,ik，那么这些整数开始时被放在带上，并用1把他们分隔开。形如 0i1 1 0i2 1 0i3 1 0ikn如果图灵机停止(不论是否在一个接受状态上)且带上为 0m，则 f(i1,i2,ik)=m f是被图灵机计算的k元函数n如果f（i1,i2,ik）对所有i1,i2,ik有定义,那么称f是一个全递归函数。全递归函数对应于递归语言，因为它总是被能停下来的图灵机所计算。n所有常用的整数算术函数都是全递归函数。15School of Computer Science&Technology,BUPT例例3 3：设计图灵机求真减法：设计图灵机求真减法n思路：思路：1.用空白符B代替带上的最左端的02右移至紧跟1后的0,将其改为13左移找到B，将B之后的0改为B4重复上述过程如果如果（1）右移找0时，遇到B，意味着mnBBB 0 m-(n+1)1 111 n+1 n个将后面n+1个1变为B，将左侧最后一个B变0，形如BBB 0 0 m-(n+1)BBB n个 n+1个 这时，带上留下m-n个0，即结果为m-nn 初始带 0m 10n16School of Computer Science&Technology,BUPT求真减法（续）求真减法（续）(2)M左移找不到0，意味着 n m，形如 BBB 1 111 00 m个 m个 n-m个 此时,用B替换所有剩余的1 和017School of Computer Science&Technology,BUPT例例4 4：L=L=0 0 m m m=2 m=2n n,n,n 0 0 n设计思路：思路：对输入串入串w w 1.从左到右扫描带，隔一个消一个0；2若带上只剩唯一一个0,接受；3若带上不止一个0,且个数为奇数，拒绝；4让读写头返回带的最左端；5.转第一步。18School of Computer Science&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=L=0 0 m m m=2 m=2n n,n,n 0 0 的的图灵机图灵机19School of Computer Science&Technology,BUPT课堂练习课堂练习n设计一一个个状状态数数不不超超过3 3的的图灵灵机机，它它能能够接接受受语言言L=a(a+b)L=a(a+b)*，若若假假定定T=a,b,T=a,b,两两个个状状态的的图灵灵机机能能否接受否接受该语言？言？20School of Computer Science&Technology,BUPT5.2 图灵机的构造技术 在设计图灵机的过程中，写出函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具。目的：设计时方便，但这些构造技术并未增加图灵机的功能。21School of Computer Science&Technology,BUPT5.2.1.利用带存储区的状态利用带存储区的状态（storage in the state）此类此类图灵机图灵机 M=(Q,q0,B,F)中，状态中可以包含中，状态中可以包含一个具有有限个取值的存储单元，即状态集合为一个具有有限个取值的存储单元，即状态集合为 Q=S T=q,a|q S a T，其中其中 q S 通常表示控制状态，而通常表示控制状态，而 a T 通常表示数据元素通常表示数据元素.一般情况下，有限控制器内允许存储一般情况下，有限控制器内允许存储n个字符，即状态的第个字符，即状态的第2个元素可存储个元素可存储n个字符。个字符。22School of Computer Science&Technology,BUPT例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视整个带，若找不到与第一个相同的字符，则整个带，若找不到与第一个相同的字符，则M接受该字符串，否则不接受。接受该字符串，否则不接受。构造构造M=(Q,a,b,a,b,B,q0,B,F)其中其中Q=q0,q1a,b,B=q0,a,q0,b,q0,Bq1,aq1,bq1,B初态初态q0,B终态终态F=q1,B 函数：函数：(q0,B,a)=(q1,a,a,R)(q0,B,b)=(q1,b,b,R)存第一个字符存第一个字符(q1,a,b)=(q1,a,b,R)(q1,b,a)=(q1,b,a,R)后面符号与第一个不等，继续右移后面符号与第一个不等，继续右移(q1,a,B)=(q1,B,B,L)(q1,b,B)=(q1,B,B,L)进入终态进入终态q1,B(q1,a,a)=(q1,b,b)=遇到相同符号，遇到相同符号，无定义无定义 M停机，不接受停机，不接受23School of Computer Science&Technology,BUPT5.2.2 多道多道（multiple tracks）图灵机）图灵机把图灵机的输入带分成两层或多层，这样，原来的每一单把图灵机的输入带分成两层或多层，这样，原来的每一单元变成了上下两个或多个单元。元变成了上下两个或多个单元。对含有对含有n层的输入带来说，读写头一次可同时读出并改写层的输入带来说，读写头一次可同时读出并改写n个单元的字符，这样的图灵机称为个单元的字符，这样的图灵机称为n道机。道机。24School of Computer Science&Technology,BUPT例：例：多道多道图灵机图灵机例：用三道机，检查某个数例：用三道机，检查某个数n（n2）是否为素数。（书）是否为素数。（书p196）思路：将被检查的数思路：将被检查的数n以二进制形式写在输入带的第一道上，数的两端分以二进制形式写在输入带的第一道上，数的两端分别用￥和别用￥和定界定界允许的输入符号为允许的输入符号为￥,B,B,0,B,B,1,B,B,B,B分别代表分别代表1，2，3带上的内容。带上的内容。检查方法：检查方法：在第二道上写下一个二进制数在第二道上写下一个二进制数2把第一道上的数复制到第三道上把第一道上的数复制到第三道上将第三道上的数减去第二道上的数，余数留在第三道上将第三道上的数减去第二道上的数，余数留在第三道上若余数为若余数为0，被检查的数不是素数，被检查的数不是素数若余数不为若余数不为0，将第二道数加，将第二道数加1，将第一道数复制到第三道，重复上述，将第一道数复制到第三道，重复上述1，2，3，4过程过程当一，二道数相等时，该数时素数。当一，二道数相等时，该数时素数。25School of Computer Science&Technology,BUPT 5.2.3 核对符核对符 当用图灵机识别语言时，如果语言中存在有重复性或可当用图灵机识别语言时，如果语言中存在有重复性或可逆性等类型的句子时，为了判定某个字符串是否属于语句中逆性等类型的句子时，为了判定某个字符串是否属于语句中的句子，可以使用一个核对符，以此增加图灵机的灵活性。的句子，可以使用一个核对符，以此增加图灵机的灵活性。考虑用一个双道机，在第二道上使用核对符考虑用一个双道机，在第二道上使用核对符“”，在，在第一道上放要被检查的字符串第一道上放要被检查的字符串,当字符串中某个字符一旦被核当字符串中某个字符一旦被核对以后对以后,可以在第二道上对应位置写上核对符可以在第二道上对应位置写上核对符“”。26School of Computer Science&Technology,BUPT例：例：核对符核对符例：设计一个图灵机例：设计一个图灵机M M，能够识别语言，能够识别语言wtwwa,b*wtwwa,b*思路：以思路：以t t为分界符，一个一个比较。为分界符，一个一个比较。解：构造解：构造M=(Q,T,qM=(Q,T,q0 0，B,F)B,F)其中其中Q=qQ=qi i,c i=1,2,c i=1,2,9,c=a,b,9,c=a,b或或BB状态第二元素可存储一个字符。状态第二元素可存储一个字符。T=cT=c，B c=a,bB c=a,b或或t t 两道与一道不同的表示法两道与一道不同的表示法cc，Y c=a,b,tY c=a,b,t或或B,Y=BB,Y=B或或 q q0 0=q=q1 1,B,F=q,B,F=q9 9,B,B空白符空白符B B在二道机下表示为在二道机下表示为BB，BB27School of Computer Science&Technology,BUPT例：例：核对符核对符28School of Computer Science&Technology,BUPT核对符例核对符例：abtab的分析过程的分析过程q1,Babtabaq2,abtababq2,atababtq3,aab abq4,Btabaq5,Bbtabq6,Babtab aq1,Bbtababq2,btababtq3,bab abtaq3,bbabtq4,Babaq5,Bbtab abq7,Btababtq8,Bababtaq8,Bb 29School of Computer Science&Technology,BUPT 5.2.4 移位移位 可以让图灵机具备移位的功能，即对输入带上的可以让图灵机具备移位的功能，即对输入带上的字符进行移位操作。当需要在输入带上留出一部分空字符进行移位操作。当需要在输入带上留出一部分空间时，可将输入带上的非空白符右移若干单元。间时，可将输入带上的非空白符右移若干单元。假设需要输入带上的非空白字符右移假设需要输入带上的非空白字符右移n n个单元，个单元，则可让控制器状态的第二个元素具有存储则可让控制器状态的第二个元素具有存储n n单元的功单元的功能（能（n n是有限数）是有限数）30School of Computer Science&Technology,BUPT例：例：构造图灵机构造图灵机M，要求它将带上非空白符向移动两个单元，要求它将带上非空白符向移动两个单元原带为原带为 a b c d B，移后为移后为 z z a b c d B设设M=(Q,T,q0,B,F)；Q=q,D1,D2 q=q0,q1,且且D1,D2,Dn初始：初始：q0,B,B,终态终态q1,B,B定义：定义：(q0,B,B,D1)=(q0,B,D1,Z,R)(q0,B,D1,D2)=(q0,D1,D2,Z,R)(q0,D1,D2,D3)=(q0,D2,D3,D1,R)(q0,Dn-1,Dn,B)=(q0,Dn,B,Dn-1,R)(q0,Dn,B,B)=(q1,B,B,Dn,L)对对D B,Z:(q1,B,B,D)=(q1,B,B,D,L)回到输入点回到输入点31School of Computer Science&Technology,BUPT 5.2.5 子程序子程序（subroutines）的设计）的设计 左上图的左上图的图灵机表示子程序图灵机表示子程序 copy，右上图的，右上图的图灵机表图灵机表示可以调用示可以调用copy 的主程序的主程序，完成两个正整数的乘法，完成两个正整数的乘法.初始初始时，带上的符号串形如时，带上的符号串形如 0m10n1，而结束时，带上的符号串，而结束时，带上的符号串变为变为0mn.
