【文章內(nèi)容簡介】 態(tài)中(5)[q， a2]， B， end_move， a2， R將最后一個符號放在帶上其中規(guī)則 (3)需要 重復多次使用。本例使用三元組表示特殊狀態(tài)也可以使用二元組表示特殊狀態(tài)如 [q， a1， a2]可以記為 [q， a1a2]（ n元組也可以表示為二元組）對帶上符號進行移動 一般只是比較復雜的 TM的識別任務(wù)中的一部分工作移動本身 不會涉及 到串的接收或拒絕問題復雜的 TM可以繼續(xù)從 end_move狀態(tài)開始其他的工作思考：構(gòu)造 TM將整個輸入串前兩個符號 刪除 。思路將帶上符號 從右向左 移動兩個單元。例 615構(gòu)造 TM輸入字母表為 {0， 1}在輸入串的開始處添加子串 10。略。例 616構(gòu)造 TMΣ={a， b， c}將整個串包含的第一個 abc子串 刪除 。思路存儲技術(shù)尋找到第 1個 abc子串的位置將后面的符號 向左 移動三個單元。略。例 618構(gòu)造 TM， 輸入字母表為 {0， 1}，要求 M接收語言 L：該語言的每個字符串 包含 且 僅只能包含一個 101子串 (有 且 僅有 一 個 101， 不可以沒有 101子串） 思路當識別出第一個 101后，檢查輸入帶上剩余的串不能再包含 10110101？TM=（ Q， ∑， start， accept， δ）Q={start， [q， 0]， [q， 1]， [q， 10]，check， [check， 0]， [check， 1]，[check， 10]， refuse， accept}∑={0， 1}∑′={0， 1， B}(1)掃描第一符號start， 0， [q， 0]， 0， Rstart， 1， [q， 1]， 1， Rstart， B， refuse， B， N空串(2)[q， 0]， 0， [q， 0]， 0， R[q， 0]， 1， [q， 1]， 1， R(3)已經(jīng)掃描到 “1”，等待可能的 “0”[q， 1]， 1， [q， 1]， 1， R[q， 1]， 0， [q， 10]， 0， R(4)已經(jīng)掃描到 “10”，等待可能的 “1”[q， 10]， 0， [q， 0]， 0， R[q,10],1， check,1， R(5)已掃描到 101，檢查串的剩余部分check， 0， [check， 0]， 0， Rcheck， 1， [check， 1]， 1， N(6)[check， 0]， 0， [check， 0]， 0， R[check， 0]， 1， [check， 1]， 1， R(7)[check， 1],0， [check， 10]， 0， R[check， 1]， 1， [check， 1]， 1， R（ 8）的第 2條指令與（ 9）可以省略(8)[check,10],0,[check， 0],0,R[check， 10],1,refuse， 1， R(9)整個輸入串中沒有 101[q， 0]， B， refuse， B， N[q， 1]， B， refuse， B， N[q， 10]， B， refuse， B， N結(jié)束(10)整個輸入串只有一個 101[check， 0]， B， accept， B， N[check， 1]， B， accept， B， N[check， 10]， B， accept， B， N思考構(gòu)造 TM，接收語言 L：該語言的每個句子必須包含 兩個 101例 619構(gòu)造 TM，接收語言 L： 該語言的每個句子 最多只能包含一個100子串（ 可以沒有 100子串 ）。思路接收 1個 100子串的所有串；接收沒有 100子串的所有串。例 623構(gòu)造 TM接收語言 L：該語言的每個句子 不包含 子串 100。思路當識別出第一個 100后，就拒絕。圖靈機掃描多個符號技術(shù)l略為了能夠保存和處理更復雜的數(shù)據(jù)，可以將 TM的輸入帶劃分為若干道在各道上可以存放不同的符號。沒有改變圖靈機的基本模型，只是將帶上符號當做一個向量的組合每個符號可以是一個 K維向量（將輸入帶劃分為 K道）。單帶 K道的圖靈機狀態(tài)轉(zhuǎn)換函數(shù)一般形式為q， x， q′， W ， {L， R， N}對于 K道圖靈機q， [ai1， ai2， … ， aik]， q′，[bi1， bi2， … ， bik]， {L， R， N}一次需要掃描一個符號的多道思考l二進制的加法l考查第 3題例 624:構(gòu)造圖靈機字母表為 {a}接收語言 L：{an|n=0，且 n為完全平方數(shù) }基本數(shù)學公式：(n+1)2=n2+2n+1思路使用三道的圖靈機第一道存放輸入串；第二、三兩道作為 “運算器 ”使用。初始時從 i=0開始在第二道上放 i2個 a比較第一道與第二道上 a的個數(shù)如果相等，就接收；不相等，則在第三道上設(shè)置 (計算 )出2*i+1個 a，將第三道上的 a加入到第二道上去，從而，在第二道上形成 (i+1)2個 a再與第一道上 a的個數(shù)進行比較。初始 i=0第 2道 a個數(shù)為 02aaa………… aBn個 aBBB…………B0 2=0BBB…………B第 3道設(shè)置為 2*0+1aaa………… aBBBB…………B0 2aBB…………B2*0+1第 2道設(shè)置為 12i=1aaa………… aBaBB…………B1 2aBB…………B第 3道設(shè)置為 2*1+1aaa………… aBnaBB…………B1 2aaaB…………B2*1+1第 2道設(shè)置為 22i=2aaa………… aBnaaaaB………B2 2aaaB…………B第 3道設(shè)置為 2*2+1aaa…………… aBnaaaaB……….…B2 2aaaaaB…………B2*2+1第 2道設(shè)置為 32i=3aaa………… aBnaaaaaaaaaB….B3 2aaaaaB………B第 3道設(shè)置為 2*3+1aaa………… aBnaaaaaaaaaB…B3 2aaaaaaaB……B2*3+1第 2道設(shè)置為 42i=4aaa………………..… aBnaaaaaaaaaaaaaaaaB…B4 2aaaaaaaB………….…B 上述動作一直重復下去，直到第一、二道上 a的個數(shù)相等，則接收；或者第一、二道 上 a的個數(shù)不相等則拒絕該輸入串。從 i=2過渡 i=3到時，圖靈機輸入帶為：lTM=（ Q， ∑， start， accept， δ）Q={start， q1， …,q9,refuse,accept}∑={a}∑′={a， B}(1)對于兩種特殊情況： n=0或者 n=1， 進行處理start,[B,B,B],accept,[B,B,B],Nstart,[a,B,B],q1， [a， B， B]， Rq1,[B,B,B],accept,[B， B， B]， N(2)i=0：準備工作q1,[a， B,B]， q9， [a， B， B]， Lq9,[a,B,B]， q2， [a， B， a]， R在第三道上放一個 aq2,[a， B,B]， q2， [a， B， B]， Rq2,[B， B,B]， q3， [B， B， B]， L(3)計算 (i+1)2其中： x， y∈ {a， B}將第３道的 a復制第 2道的 a的后面① 向左找 復制標志 b或 ┣q3,[a， x， y]， q3， [a， x， y]， Lq3， ┣ ， q4， ┣ ， Rq3,[a， a， b]， q4， [a， a， a]， R② 建立新標志q4,[a,B,a]， q4， [a， a， a]， R(i=0)q4,[a， a， a]， q5， [a， a， b]， R//在第三道上放 b為新標志其中： x∈ {a， B}③ 在第二道上復制一個 aq5,[a， a， x]， q5， [a， a， x]， Rq5,[a， B， x]， q3， [a， a， x]， L其中： x∈ {a， B}(4)計算 2(i+1)+1， 為下次做準備(實際上 ,在第 3道每次增加 2個 a)q4,[a， x， B]， q6， [a， x， a]， Rq6,[a， x， B]， q7， [a， x， a]， Rq6,[B， B， B]， q7， [B， B， a]， L僅當 輸 入串 為 a4和 a9時 (i2=2*i)其中： x， y∈ {a， B}(5)比較第一道和第二道上 a的個數(shù)q7,[a， x， y]， q7， [a， x， y]， Rq7,[B， B,B]， q8， [B， B， B]， L//第一道上 a的已經(jīng)查完其中： x∈ {a， B}q7,[B， B， a],q8， [B， B， a]， L僅當 輸 入串 為 a4和 a9時 (i2小于 2i)q8,[a,a,x],accept,[a， a， x]， Nq8,[a， B， x]， q3， [a， B， x]， L第二道的 a少于第一道的 a，繼續(xù)掃描(6)拒絕情況 (可省略 )q5,[B,B,B],refuse,[B， B， B]， N第二道的 a多于第一道上的 a， 停機q5,[B,B,a],refuse,[B， B， a]， N第一道上已經(jīng)沒有 a， 停機 在 TM的工作中，有時需要對已經(jīng)掃描過的符號進行檢查。為了區(qū)分帶上的某個符號是否已經(jīng)檢查過，可以使用查訖符號 “√”進行標記需要使用多道技術(shù)存儲查訖符號初始時，所有帶上符號的查訖標記都標記為 “B”。例 625構(gòu)造 TML(M)={w2w|w∈ {0， 1}+}分析依次比較 2前后的符號將帶分成兩條道第一條道上存放輸入符號串第二條道上存放檢查標記 。初始輸入帶上的符號情況為： ┣ a1a2…a n2b1b2… bmB…┣ BB…BBBB…BB…比較時，使用存儲技術(shù)，將符號 “2”前面的待比較符號 存儲 ，再與 2后面 相應(yīng)位置 的符號進行比較。某個時刻，輸入帶上的符號情況 ┣ a1a2…a n2b1b2… bmB…┣ ??…BB ?B…BB…M的初始狀態(tài)為 start令 a=0或 1， b=0或 1start， ┣ ， [q1， B]， ┣ ， R記錄待比較符號：[q1,B