最新形式语言自动机——图灵机(一)PPT课件.ppt
形式语言自动机形式语言自动机图灵机图灵机(一一)主要内容主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点:TM的定义、TM的构造。n难点:TM的构造。2School 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还在某个在某个输入上运行，我入上运行，我们无法知道是因无法知道是因为运行的运行的时间不不够长而没有被接受，而没有被接受，还是根本就不会停机）是根本就不会停机）图灵机的停机问题图灵机的停机问题 9School of Computer Science&Technology,BUPT图灵机举例图灵机举例例例1 1：设语言言 L=anbnn=1，设计图灵机接受灵机接受L。思路：最初思路：最初带上上为aa abbbBBBn个个an个个b首先用首先用x替替换M最左最左边的的a，再右移至最左再右移至最左边的的b用用y替替换之，左移之，左移寻找最右的找最右的x，然后右移一然后右移一单元到最左的元到最左的a，重复循重复循环。如果如果（1 1）当在搜）当在搜寻b时，M找到了空白符找到了空白符B，则M停止，不接受停止，不接受该串。串。（此（此时，a的个数大于的个数大于b的个数）的个数）（2 2）当将当将b改改为y后，左后，左边再也找不到再也找不到a，此此时,若右若右边再无再无b，接受；若仍有接受；若仍有b，则b的个数大于的个数大于a的个数，不接受。的个数，不接受。10School of Computer Science&Technology,BUPT例例1L=anbnn=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 11School of Computer Science&Technology,BUPT对于输入字符串对于输入字符串001122，该图灵机可以有如下推导该图灵机可以有如下推导步：步：q0001122MXq101122 MX0q11122MX0Yq2122MX0Y1q222MX0Yq31Z2*Mq3X0Y1Z2MXq00Y1Z2*MXXYYZq22MXXYYq3ZZ*MXq3XYYZZMXXq0YYZZ*MXXYYq4ZZMXXYYZq5ZMXXYYZZq5BMXXYYZZBq6B例例2L=0n1n2n n 1.12School of Computer Science&Technology,BUPT 转移图与转移表转移图与转移表13School 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所有常用的整数算术函数都是全递归函数。14School of Computer Science&Technology,BUPT例例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 10n15School of Computer Science&Technology,BUPT求真减法（求真减法（续）(2)M左移找不到0，意味着n m，形如 BBB 1 111 00 m个 m个 n-m个 此时,用B替换所有剩余的1和016School of Computer Science&Technology,BUPT例例4：L=L=0 0 m m m=2 m=2n n,n,n 0 0 n设计思路：思路：对输入串入串w1.从左到右扫描带，隔一个消一个0；2若带上只剩唯一一个0,接受；3若带上不止一个0,且个数为奇数，拒绝；4让读写头返回带的最左端；5.转第一步。17School 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 的的图灵机灵机18School of Computer Science&Technology,BUPT课堂练习课堂练习n设计一一个个状状态数数不不超超过3的的图灵灵机机，它它能能够接接受受语言言L=a(a+b)*，若若假假定定T=a,b,两两个个状状态的的图灵灵机机能能否接受否接受该语言？言？19School of Computer Science&Technology,BUPT5.2 图灵机的构造技术 在设计图灵机的过程中，写出函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具。目的：设计时方便，但这些构造技术并未增加图灵机的功能。20School 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个字符。个字符。21School 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停机，不接受停机，不接受22School of Computer Science&Technology,BUPT5.2.2 多道多道（multiple tracks）图灵机）图灵机把图灵机的输入带分成两层或多层，这样，原来的每一单把图灵机的输入带分成两层或多层，这样，原来的每一单元变成了上下两个或多个单元。元变成了上下两个或多个单元。对含有对含有n层的输入带来说，读写头一次可同时读出并改写层的输入带来说，读写头一次可同时读出并改写n个单元的字符，这样的图灵机称为个单元的字符，这样的图灵机称为n道机。道机。23School 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过程过程当一，二道数相等时，该数时素数。当一，二道数相等时，该数时素数。24School of Computer Science&Technology,BUPT 5.2.3 核对符核对符当用当用图灵机灵机识别语言言时，如果，如果语言中存在有重复性或可言中存在有重复性或可逆性等逆性等类型的句子型的句子时，为了判定某个字符串是否属于了判定某个字符串是否属于语句中句中的句子，可以使用一个核的句子，可以使用一个核对符，以此增加符，以此增加图灵机的灵活性。灵机的灵活性。考考虑用一个双道机，在第二道上使用核用一个双道机，在第二道上使用核对符符“”，在，在第一道上放要被第一道上放要被检查的字符串的字符串,当字符串中某个字符一旦被核当字符串中某个字符一旦被核对以后以后,可以在第二道上可以在第二道上对应位置写上核位置写上核对符符“”。25School of Computer Science&Technology,BUPT例：例：核对符核对符例：例：设计一个一个图灵机灵机M，能，能够识别语言言wtww a,b*思路：以思路：以t为分界符，一个一个比分界符，一个一个比较。解：构造解：构造M=(Q,T,q0，B,F)其中其中Q=qi,ci=1,2,9,c=a,b或或B状状态第二元素可存第二元素可存储一个字符。一个字符。T=c，Bc=a,b或或t两道与一道不同的表示法两道与一道不同的表示法c，Yc=a,b,t或或B,Y=B或或 q0=q1,B,F=q9,B空白符空白符B在二道机下表示在二道机下表示为B，B26School of Computer Science&Technology,BUPT例：例：核对符核对符27School 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 28School of Computer Science&Technology,BUPT 5.2.4 移位移位可以可以让图灵机具灵机具备移位的功能，即移位的功能，即对输入入带上的上的字符字符进行移位操作。当需要在行移位操作。当需要在输入入带上留出一部分空上留出一部分空间时，可将，可将输入入带上的非空白符右移若干上的非空白符右移若干单元。元。假假设需要需要输入入带上的非空白字符右移上的非空白字符右移n个个单元，元，则可可让控制器状控制器状态的第二个元素具有存的第二个元素具有存储n单元的功元的功能（能（n是有限数）是有限数）29School 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)回到输入点回到输入点30School of Computer Science&Technology,BUPT 5.2.5 子程序子程序（subroutines）的设计）的设计左上图的左上图的图灵机表示子程序图灵机表示子程序 copy，右上图的，右上图的图灵机表图灵机表示可以调用示可以调用copy的主程序的主程序，完成两个正整数的乘法，完成两个正整数的乘法.初始初始时，带上的符号串形如时，带上的符号串形如0m10n1，而结束时，带上的符号串，而结束时，带上的符号串变为变为0mn.31School of Computer Science&Technology,BUPT结束语结束语谢谢大家聆听！谢谢大家聆听！32
