《形式語(yǔ)言自動(dòng)機(jī)-圖靈機(jī).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《形式語(yǔ)言自動(dòng)機(jī)-圖靈機(jī).ppt（31頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1,SchoolofComputerScience&Technology,BUPT,第五章圖靈機(jī),A.Turing在1936年介紹了這樣一個(gè)通用的計(jì)算模型，該模型具有以下兩個(gè)性質(zhì)該模型的每個(gè)過(guò)程都是有窮可描述的；過(guò)程必須是由離散的、可以機(jī)械執(zhí)行的步驟組成。圖靈機(jī)是計(jì)算機(jī)的一種簡(jiǎn)單數(shù)字模型，盡管簡(jiǎn)單，但它具有模擬通用計(jì)算機(jī)的計(jì)算能力。通過(guò)研究TM來(lái)研究遞歸可枚舉集和部分遞歸函數(shù)為算法和可計(jì)算性研究提供了形式化描述工具。,2,SchoolofComputerScience&Technology,BUPT,主要內(nèi)容,TM的基本定義TM的格局TM接受的語(yǔ)言TM的構(gòu)造技術(shù)TM的變形；重點(diǎn):TM的定義、TM的構(gòu)造。難點(diǎn):TM的構(gòu)造。,3,SchoolofComputerScience&Technology,BUPT,讀寫頭在每一時(shí)刻掃描帶上的一個(gè)單元帶有一個(gè)最左單元，向右則是無(wú)限的。帶的每個(gè)單元可容納一個(gè)帶符號(hào)開始時(shí)，最左邊n個(gè)單元裝著輸入（n>＝0，n為有限數(shù)），它是一個(gè)字符串，符號(hào)都選自“帶符號(hào)”的一個(gè)子集，即所謂的“輸入符號(hào)集合”。余下的有窮個(gè)單元都存放空白符，它是一個(gè)特殊的帶符號(hào)，但不是輸入符號(hào)。,圖靈機(jī)的基本模型,4,SchoolofComputerScience&Technology,BUPT,在一個(gè)圖靈機(jī)的動(dòng)作中，圖靈機(jī)根據(jù)帶頭（讀寫頭）所掃描的符號(hào)和有限控制器的狀態(tài)可能作改變狀態(tài)在被掃描的帶單元上重新寫一個(gè)符號(hào)，以代替原來(lái)寫在該單元上的符號(hào).將帶頭向左或者右移一個(gè)單元。*圖靈機(jī)和雙向有限自動(dòng)機(jī)的區(qū)別：圖靈機(jī)能改變它帶上的符號(hào)。,圖靈機(jī)的工作機(jī)制,5,SchoolofComputerScience&Technology,BUPT,圖靈機(jī)的形式化描述,有限狀態(tài)集有限輸入符號(hào)集有限帶符號(hào)集轉(zhuǎn)移函數(shù)開始狀態(tài)特殊帶符:空白符終態(tài)集合,q0?QT??B??–TF?Q,轉(zhuǎn)移函數(shù)?:Q???Q???{L,R},形式定義一個(gè)圖靈機(jī)TM(Turingmachine)是一個(gè)七元組M=(Q,T,?,?,q0,B,F).,6,SchoolofComputerScience&Technology,BUPT,δ函數(shù)示例：Q∑→Q∑{L,R}δ(q,ai)=(p,B,L)q,p∈Qδ(q,ai)=(p,b,R)ai∈∑b∈∑格局用w1qw2描述圖靈機(jī)的瞬間工作狀態(tài)q為M的當(dāng)前狀態(tài)，w1w2∈∑*w1w2是當(dāng)前時(shí)刻從開始端（因?yàn)榭蓪懀┑接疫吙瞻追?hào)為止的內(nèi)容當(dāng)讀寫頭已達(dá)到帶的右端，則w1w2為讀寫頭以左的內(nèi)容。約定：w1qw2表示讀寫頭正掃描w2的最左字符w2＝?則表示讀寫頭正掃描一個(gè)空白字符。,圖靈機(jī)的函數(shù)與格局,7,SchoolofComputerScience&Technology,BUPT,圖靈機(jī)的格局,給定圖靈機(jī)M=(Q,T,?,?,q0,B,F)，定義格局之間的推導(dǎo)關(guān)系├M如下：1.設(shè)?(q,Xi)=(p,Y,L)，則有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-2pXi-1Y…Xn，但有如下兩個(gè)例外：（1）i=1時(shí)，qX1X2…Xn├MqYX2…Xn，和（2）i=n及Y=B時(shí)，X1X2…Xn-1qXn├MX1X2…Xn-2pXn-1B.2.設(shè)?(q,Xi)=(p,Y,R)，則有X1X2…Xi-1qXiXi+1…Xn├MX1X2…Xi-1YpXi+1…Xn，但有如下兩個(gè)例外：（1）i=n時(shí)，X1X2…Xn-1qXn├MX1X2…Xn-1YpB，和（2）i=1及Y=B時(shí)，qX1X2…Xn├MBpX2…Xn-1Xn.,8,SchoolofComputerScience&Technology,BUPT,圖靈機(jī)接受的語(yǔ)言,L(M)={ω│ω∈T*且q0ω├*α1pα2,p∈F,α1α2∈∑*}圖靈機(jī)接受的語(yǔ)言是輸入字母表中這樣一些字符串的集合，初始時(shí)，這些字符串放在M的帶上，M處于狀態(tài)q0，且M的帶頭處在最左單元上，這些字符串將使M進(jìn)入某個(gè)終止?fàn)顟B(tài)。假定：當(dāng)輸入被接受時(shí)，圖靈機(jī)將停止，沒有下一個(gè)動(dòng)作。,9,SchoolofComputerScience&Technology,BUPT,任給圖靈機(jī)M=(Q,T,?,?,q0,B,F)，以及輸入字符串w?T*.試問(wèn)：對(duì)于w，M是否停機(jī)？停機(jī)是指圖靈機(jī)不存在下一個(gè)移動(dòng)步（move）.結(jié)論圖靈機(jī)的停機(jī)問(wèn)題是不可解的（即不可判定的）.結(jié)論任給圖靈機(jī)M，很容易構(gòu)造一個(gè)圖靈機(jī)M?，使得L(M)=L(M?)，并滿足：如果w?L(M)，則對(duì)于w，M?接受w并一定停機(jī).如果沒有特別指出，總是假定圖靈機(jī)到達(dá)終態(tài)（接受態(tài)）后一定停機(jī).但是，對(duì)不能接受的字符串，圖靈機(jī)可能永不停止.（只要M還在某個(gè)輸入上運(yùn)行，我們無(wú)法知道是因?yàn)檫\(yùn)行的時(shí)間不夠長(zhǎng)而沒有被接受，還是根本就不會(huì)停機(jī)）,,圖靈機(jī)的停機(jī)問(wèn)題,10,SchoolofComputerScience&Technology,BUPT,圖靈機(jī)舉例,例1：設(shè)語(yǔ)言L={anbn│n>=1}，設(shè)計(jì)圖靈機(jī)接受L。思路：最初帶上為aa…abb…bBBB……n個(gè)an個(gè)b首先用x替換M最左邊的a，再右移至最左邊的b用y替換之，左移尋找最右的x，然后右移一單元到最左的a，重復(fù)循環(huán)。如果（1）當(dāng)在搜尋b時(shí)，M找到了空白符B，則M停止，不接受該串。（此時(shí)，a的個(gè)數(shù)大于b的個(gè)數(shù)）（2）當(dāng)將b改為y后，左邊再也找不到a，此時(shí),若右邊再無(wú)b，接受；若仍有b，則b的個(gè)數(shù)大于a的個(gè)數(shù)，不接受。,11,SchoolofComputerScience&Technology,BUPT,例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├xxyyq4,12,SchoolofComputerScience&Technology,BUPT,對(duì)于輸入字符串001122，該圖靈機(jī)可以有如下推導(dǎo)步：,q0001122,├M,Xq101122,├M,X0q11122,├M,X0Yq2122,├M,X0Y1q222,├M,X0Yq31Z2,├*M,q3X0Y1Z2,├M,Xq00Y1Z2,├*M,XXYYZq22,├M,XXYYq3ZZ,├*M,Xq3XYYZZ,├M,XXq0YYZZ,├*M,XXYYq4ZZ,├M,XXYYZq5Z,├M,XXYYZZq5B,├M,XXYYZZBq6B,例2L=?0n1n2n?n?1?.,13,SchoolofComputerScience&Technology,BUPT,轉(zhuǎn)移圖與轉(zhuǎn)移表,14,SchoolofComputerScience&Technology,BUPT,作為整數(shù)函數(shù)計(jì)算機(jī)的圖靈機(jī),預(yù)備知識(shí)：圖靈機(jī)除了作為語(yǔ)言接受器外，還可看作整數(shù)到整數(shù)的函數(shù)計(jì)算機(jī)。傳統(tǒng)方法把整數(shù)表示成一進(jìn)制整數(shù)i?0用字符串0i表示如果一個(gè)函數(shù)有k個(gè)自變量，i1,i2,…ik，那么這些整數(shù)開始時(shí)被放在帶上，并用1把他們分隔開。形如0i110i210i3…10ik如果圖靈機(jī)停止(不論是否在一個(gè)接受狀態(tài)上)且?guī)蠟?m，則f(i1,i2,…,ik)=mf是被圖靈機(jī)計(jì)算的k元函數(shù)如果f（i1,i2…,ik）對(duì)所有i1,i2…,ik有定義,那么稱f是一個(gè)全遞歸函數(shù)。全遞歸函數(shù)對(duì)應(yīng)于遞歸語(yǔ)言，因?yàn)樗偸潜荒芡Ｏ聛?lái)的圖靈機(jī)所計(jì)算。所有常用的整數(shù)算術(shù)函數(shù)都是全遞歸函數(shù)。,15,SchoolofComputerScience&Technology,BUPT,例3：設(shè)計(jì)圖靈機(jī)求真減法,思路：1.用空白符B代替帶上的最左端的02．右移至緊跟1后的0,將其改為13．左移找到B，將B之后的0改為B4．重復(fù)上述過(guò)程如果（1）右移找0時(shí)，遇到B，意味著m>nBB…B0m-(n+1)111…1n+1n個(gè)將后面n+1個(gè)1變?yōu)锽，將左側(cè)最后一個(gè)B變0，形如BB…B00m-(n+1)BB…Bn個(gè)n+1個(gè)這時(shí)，帶上留下m-n個(gè)0，即結(jié)果為m-n,初始帶0m10n,16,SchoolofComputerScience&Technology,BUPT,求真減法（續(xù)）,(2)M左移找不到0，意味著n?m，形如BB…B111…10…0m個(gè)m個(gè)n-m個(gè)此時(shí),用B替換所有剩余的1和0,17,SchoolofComputerScience&Technology,BUPT,例4：L=?0m?m=2n,n?0?,設(shè)計(jì)思路：對(duì)輸入串w1.從左到右掃描帶，隔一個(gè)消一個(gè)0；2．若帶上只剩唯一一個(gè)0,接受；3．若帶上不止一個(gè)0,且個(gè)數(shù)為奇數(shù)，拒絕；4．讓讀寫頭返回帶的最左端；5.轉(zhuǎn)第一步。,18,SchoolofComputerScience&Technology,BUPT,識(shí)別L=?0m?m=2n,n?0?的圖靈機(jī),19,SchoolofComputerScience&Technology,BUPT,課堂練習(xí),設(shè)計(jì)一個(gè)狀態(tài)數(shù)不超過(guò)3的圖靈機(jī)，它能夠接受語(yǔ)言L=a(a+b)*，若假定T={a,b},兩個(gè)狀態(tài)的圖靈機(jī)能否接受該語(yǔ)言？,20,SchoolofComputerScience&Technology,BUPT,5.2圖靈機(jī)的構(gòu)造技術(shù),在設(shè)計(jì)圖靈機(jī)的過(guò)程中，寫出δ函數(shù)很麻煩，為了構(gòu)造復(fù)雜的圖靈機(jī)，需探討圖靈機(jī)的若干構(gòu)造技術(shù)，并引入一些新的概念和工具。目的：設(shè)計(jì)時(shí)方便，但這些構(gòu)造技術(shù)并未增加圖靈機(jī)的功能。,21,SchoolofComputerScience&Technology,BUPT,5.2.1.利用帶存儲(chǔ)區(qū)的狀態(tài)（storageinthestate）,此類圖靈機(jī)M=(Q,?,?,?,q0,B,F)中，狀態(tài)中可以包含一個(gè)具有有限個(gè)取值的存儲(chǔ)單元，即狀態(tài)集合為Q=S?T={[q,a]|q?S?a?T}，其中q?S通常表示控制狀態(tài)，而a?T通常表示數(shù)據(jù)元素.一般情況下，有限控制器內(nèi)允許存儲(chǔ)n個(gè)字符，即狀態(tài)的第2個(gè)元素可存儲(chǔ)n個(gè)字符。,,22,SchoolofComputerScience&Technology,BUPT,例：設(shè)計(jì)一個(gè)圖靈機(jī)，讀寫頭將掃視第一個(gè)字符存入有限控制器內(nèi)，然后掃視整個(gè)帶，若找不到與第一個(gè)相同的字符，則M接受該字符串，否則不接受。構(gòu)造M=(Q,{a,b},{a,b,B},δ,q0,B,F)其中Q={q0,q1}{a,b,B}={[q0,a],[q0,b],[q0,B][q1,a][q1,b][q1,B]}初態(tài)[q0,B]終態(tài)F={[q1,B]}δ函數(shù)：δ([q0,B],a)=([q1,a],a,R)δ([q0,B],b)=([q1,b],b,R)存第一個(gè)字符δ([q1,a],b)=([q1,a],b,R)δ([q1,b],a)=([q1,b],a,R)后面符號(hào)與第一個(gè)不等，繼續(xù)右移δ([q1,a],B)=([q1,B],B,L)δ([q1,b],B)=([q1,B],B,L)進(jìn)入終態(tài)[q1,B]δ([q1,a],a)=Фδ([q1,b],b)=Ф遇到相同符號(hào)，δ無(wú)定義M停機(jī)，不接受,23,SchoolofComputerScience&Technology,BUPT,5.2.2多道（multipletracks）圖靈機(jī),把圖靈機(jī)的輸入帶分成兩層或多層，這樣，原來(lái)的每一單元變成了上下兩個(gè)或多個(gè)單元。對(duì)含有n層的輸入帶來(lái)說(shuō)，讀寫頭一次可同時(shí)讀出并改寫n個(gè)單元的字符，這樣的圖靈機(jī)稱為n道機(jī)。,24,SchoolofComputerScience&Technology,BUPT,例：多道圖靈機(jī),例：用三道機(jī)，檢查某個(gè)數(shù)n（n>2）是否為素?cái)?shù)。（書p196）思路：將被檢查的數(shù)n以二進(jìn)制形式寫在輸入帶的第一道上，數(shù)的兩端分別用￥和Ф定界允許的輸入符號(hào)為[￥,B,B],[0,B,B],[1,B,B],[Ф,B,B][…]分別代表1，2，3帶上的內(nèi)容。檢查方法：在第二道上寫下一個(gè)二進(jìn)制數(shù)2把第一道上的數(shù)復(fù)制到第三道上將第三道上的數(shù)減去第二道上的數(shù)，余數(shù)留在第三道上若余數(shù)為0，被檢查的數(shù)不是素?cái)?shù)若余數(shù)不為0，將第二道數(shù)加1，將第一道數(shù)復(fù)制到第三道，重復(fù)上述1，2，3，4過(guò)程當(dāng)一，二道數(shù)相等時(shí)，該數(shù)時(shí)素?cái)?shù)。,25,SchoolofComputerScience&Technology,BUPT,5.2.3核對(duì)符,當(dāng)用圖靈機(jī)識(shí)別語(yǔ)言時(shí)，如果語(yǔ)言中存在有重復(fù)性或可逆性等類型的句子時(shí)，為了判定某個(gè)字符串是否屬于語(yǔ)句中的句子，可以使用一個(gè)核對(duì)符，以此增加圖靈機(jī)的靈活性?？紤]用一個(gè)雙道機(jī)，在第二道上使用核對(duì)符“?”，在第一道上放要被檢查的字符串,當(dāng)字符串中某個(gè)字符一旦被核對(duì)以后,可以在第二道上對(duì)應(yīng)位置寫上核對(duì)符“?”。,26,SchoolofComputerScience&Technology,BUPT,例：核對(duì)符,例：設(shè)計(jì)一個(gè)圖靈機(jī)M，能夠識(shí)別語(yǔ)言{wtw│w∈{a,b}*}思路：以t為分界符，一個(gè)一個(gè)比較。解：構(gòu)造M=(Q,T,∑,δ,q0，B,F)其中Q={[qi,c]│i=1,2,…,9,c=a,b或B}狀態(tài)第二元素可存儲(chǔ)一個(gè)字符。T={[c，B]}│c=a,b或t}兩道與一道不同的表示法∑＝{[c，Y]}│c=a,b,t或B,Y=B或?}q0=[q1,B],F={[q9,B]}空白符B在二道機(jī)下表示為[B，B],27,SchoolofComputerScience&Technology,BUPT,例：核對(duì)符,,28,SchoolofComputerScience&Technology,BUPT,核對(duì)符例：abtab的分析過(guò)程,,[q1,B]abtab├a[q2,a]btab├ab[q2,a]tab├abt[q3,a]ab???├ab[q4,B]tab├a[q5,B]btab├[q6,B]abtab??????├a[q1,B]btab├ab[q2,b]tab├abt[q3,b]ab???????├abta[q3,b]b├abt[q4,B]ab├a[q5,B]btab???????????├ab[q7,B]tab├abt[q8,B]ab├abta[q8,B]b…????????????,29,SchoolofComputerScience&Technology,BUPT,5.2.4移位,可以讓圖靈機(jī)具備移位的功能，即對(duì)輸入帶上的字符進(jìn)行移位操作。當(dāng)需要在輸入帶上留出一部分空間時(shí)，可將輸入帶上的非空白符右移若干單元。假設(shè)需要輸入帶上的非空白字符右移n個(gè)單元，則可讓控制器狀態(tài)的第二個(gè)元素具有存儲(chǔ)n單元的功能（n是有限數(shù)）,30,SchoolofComputerScience&Technology,BUPT,例：構(gòu)造圖靈機(jī)M，要求它將帶上非空白符向移動(dòng)兩個(gè)單元,原帶為abcdB，移后為zzabcdB設(shè)M=(Q,T,∑,δ,q0,B,F)；Q={[q,D1,D2]│q=q0,q1,且D1,D2,…Dn∈∑}初始：[q0,B,B],終態(tài)[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)對(duì)D∈∑－{B,Z}:δ([q1,B,B],D)=([q1,B,B],D,L)回到輸入點(diǎn),31,SchoolofComputerScience&Technology,BUPT,5.2.5子程序（subroutines）的設(shè)計(jì),左上圖的圖靈機(jī)表示子程序copy，右上圖的圖靈機(jī)表示可以調(diào)用copy的主程序，完成兩個(gè)正整數(shù)的乘法.初始時(shí)，帶上的符號(hào)串形如0m10n1，而結(jié)束時(shí)，帶上的符號(hào)串變?yōu)?mn.,