計(jì)算理論_計(jì)算模型CH1_2016new

1、教材教材: 1王王 王曉東王曉東,計(jì)算機(jī)算法設(shè)計(jì)與分析計(jì)算機(jī)算法設(shè)計(jì)與分析(第第4版版),電子工業(yè)電子工業(yè). 2S 唐常杰等譯唐常杰等譯, Sipser著著, 計(jì)算理論導(dǎo)引計(jì)算理論導(dǎo)引, 機(jī)械工業(yè)機(jī)械工業(yè). 參考資料參考資料:3C 潘金貴等譯潘金貴等譯, Cormen等著等著, 算法導(dǎo)論算法導(dǎo)論, 機(jī)械工業(yè)機(jī)械工業(yè). 4M 黃林鵬等譯黃林鵬等譯, Manber著著, 算法引論算法引論-一種創(chuàng)造性方法一種創(chuàng)造性方法, 電子電子. 5劉劉 劉汝佳等劉汝佳等, 算法藝術(shù)與信息學(xué)競(jìng)賽算法藝術(shù)與信息學(xué)競(jìng)賽, 清華大學(xué)清華大學(xué).6L Lewis等著等著, 計(jì)算理論基礎(chǔ)計(jì)算理論基礎(chǔ), 清華大學(xué)清華大學(xué). 計(jì)

2、算理論與計(jì)算理論與算法分析設(shè)計(jì)算法分析設(shè)計(jì) 劉劉 慶慶 暉暉 計(jì)算理論計(jì)算理論 第一部分第一部分 計(jì)算模型計(jì)算模型 S第第1章章 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 第第2章章 上下文無(wú)關(guān)語(yǔ)言上下文無(wú)關(guān)語(yǔ)言 第第3章章 圖靈機(jī)圖靈機(jī) 第第1章章 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 從字符串匹配問(wèn)題說(shuō)起從字符串匹配問(wèn)題說(shuō)起 輸入輸入: 兩個(gè)字符串兩個(gè)字符串x, y, (|x|=n, |y|=m) 輸出輸出: 所有所有y在在x中出現(xiàn)的起點(diǎn)位置中出現(xiàn)的起點(diǎn)位置 例例: x=abaabababbabababbababaa, y=ababbababaa 輸出輸出13 直接法直接法: 以每個(gè)位置為起點(diǎn)對(duì)比一遍以每個(gè)位置為起點(diǎn)對(duì)比一遍

3、y. O(n-m+1)m) 觀察改進(jìn)方法觀察改進(jìn)方法 x: a b a a b a b a b b a b a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a y: |a b a b b a b a b a a 構(gòu)造狀態(tài)和轉(zhuǎn)移函數(shù)構(gòu)造狀態(tài)和轉(zhuǎn)移函數(shù)y=ababbababaa 0 1a2ab3aba4abab5ababb11ababbababaa10ababbababa9ababbabab8ababbaba7ababbab6ababbaaaaaaab

4、bbbbbbbbaaaaabbaf: 0:11 a,b 0:11 x: a b a a b a b a b b a b a b a b b a b a b a a 0 1 2 3 1 2 3 4 3 4 5 6 7 8 9 10 4 5 6 7 8 9 10 11 輸出輸出 23-10 = 13 b輸入輸入x,y, 串匹配的有限自動(dòng)機(jī)算法串匹配的有限自動(dòng)機(jī)算法符號(hào)集符號(hào)集 , m=Length(y), 計(jì)算計(jì)算轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù), Yi=y1y2yi. 1. 對(duì)對(duì) q = 0:m 2. 對(duì)每個(gè)符號(hào)對(duì)每個(gè)符號(hào)a , 3. k=minm,q+1 4. 當(dāng)當(dāng) Yk不是不是Yqa的后綴的后綴, k- 5

5、. f(q,a)=k = a,bf(0,a)=1, f(0,b)=0, abab|b, f(4,b)=5,abab|a, f(4,a)=3, 匹配算法匹配算法 1. n=Length(x), q=0 2. 對(duì)對(duì) i = 1:n 3. q=f(q,xi), 4. 若若q=m, 打印打印 i-m+1 字符串匹配算法字符串匹配算法算法算法預(yù)處理時(shí)間預(yù)處理時(shí)間匹配時(shí)間匹配時(shí)間樸素樸素0O(n-m+1)m)自動(dòng)機(jī)自動(dòng)機(jī)O(m| |) (n)Knuth-Morris-Pratt (m) (n)其中其中 是字母表是字母表 字符串與語(yǔ)言字符串與語(yǔ)言字母表字母表: 任意一個(gè)有限集任意一個(gè)有限集. 常用記號(hào)常用記

6、號(hào) , . 符號(hào)符號(hào): 字母表中的元素字母表中的元素字符串字符串: 字母表中符號(hào)組成的字母表中符號(hào)組成的有限序列有限序列 如如asdf, 通俗地說(shuō)即單詞通俗地說(shuō)即單詞串的串的長(zhǎng)度長(zhǎng)度|, 例例: |abcde|=5 串的串的連接連接*, 例例: (abc)*(de)=abcde 串的串的反轉(zhuǎn)反轉(zhuǎn)R, 例例: (abcde)R=edcba空詞空詞: 記為記為 , 長(zhǎng)度為長(zhǎng)度為0 語(yǔ)言語(yǔ)言: 給定字母表上一些給定字母表上一些字符串的集合字符串的集合 * *, ,語(yǔ)言語(yǔ)言, ,字典序字典序取字母表取字母表 = 0,1, 上的語(yǔ)言舉例上的語(yǔ)言舉例: A=0,00,0000, B=0,00,01,000

7、,001,l 上所有有限長(zhǎng)串記為上所有有限長(zhǎng)串記為 *. l 上上的任一語(yǔ)言都是的任一語(yǔ)言都是 *的子集的子集.l *(字典序字典序): , 0, 1, 00, 01, 10, 11, 000, l 上所有無(wú)限長(zhǎng)串記為上所有無(wú)限長(zhǎng)串記為 N. l 上的語(yǔ)言與上的語(yǔ)言與 N一一對(duì)應(yīng)一一對(duì)應(yīng). * 0100011011000 001 B 0 0001 000 001 f(B)010110011等勢(shì)等勢(shì), ,可數(shù)可數(shù), ,不可數(shù)不可數(shù)l等勢(shì)等勢(shì): 若兩集合間存在一一對(duì)應(yīng)若兩集合間存在一一對(duì)應(yīng), 則稱它們等勢(shì)則稱它們等勢(shì) l可數(shù)可數(shù): 若若集合與集合與有限集或有限集或與自然數(shù)集等與自然數(shù)集等勢(shì)勢(shì) 或者

8、說(shuō)集合元素可以按次序列出或者說(shuō)集合元素可以按次序列出l不可數(shù)不可數(shù): 若集合不是可數(shù)的若集合不是可數(shù)的 或者說(shuō)集合元素不能按次序列出或者說(shuō)集合元素不能按次序列出l * 可數(shù)可數(shù) l N 不可數(shù)不可數(shù)(與與0,1中全體實(shí)數(shù)一一對(duì)應(yīng)中全體實(shí)數(shù)一一對(duì)應(yīng))l 上上的全體語(yǔ)言不可數(shù)的全體語(yǔ)言不可數(shù) 決定性問(wèn)題與語(yǔ)言一一對(duì)應(yīng)決定性問(wèn)題與語(yǔ)言一一對(duì)應(yīng)決定性問(wèn)題決定性問(wèn)題(Dicision Prob): 只需回答是與否的問(wèn)題只需回答是與否的問(wèn)題 “一數(shù)是否是偶數(shù)一數(shù)是否是偶數(shù)” - 以以0結(jié)尾的結(jié)尾的01串串 “串串0,1個(gè)數(shù)是否相等個(gè)數(shù)是否相等”- 0,1個(gè)數(shù)相等的個(gè)數(shù)相等的01串串 “串長(zhǎng)度是否是串長(zhǎng)度是

9、否是2的冪次的冪次”- 02n : n 0 “圖是否連通圖是否連通”- | G是連通圖是連通圖 其中其中是圖是圖G編碼成的字符串編碼成的字符串.給定有限字母表給定有限字母表 , 每個(gè)輸入是一個(gè)串每個(gè)輸入是一個(gè)串, 任意串都可以是輸入串任意串都可以是輸入串 一個(gè)決定性問(wèn)題是滿足某性質(zhì)的串的集合一個(gè)決定性問(wèn)題是滿足某性質(zhì)的串的集合(語(yǔ)言語(yǔ)言) 當(dāng)機(jī)器從簡(jiǎn)單到復(fù)雜當(dāng)機(jī)器從簡(jiǎn)單到復(fù)雜, 能解決的問(wèn)題也變復(fù)雜能解決的問(wèn)題也變復(fù)雜確定型有限確定型有限(窮窮)自動(dòng)機(jī)的形式定義自動(dòng)機(jī)的形式定義定義定義: 有限自動(dòng)機(jī)有限自動(dòng)機(jī)是一個(gè)是一個(gè)5元組元組(Q, , ,s,F),1) Q是是有限集有限集, 稱為稱為狀態(tài)

10、集狀態(tài)集;2) 是是有限集有限集, 稱為稱為字母表字母表;3) : Q Q是是轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù);4) s Q是是起始狀態(tài)起始狀態(tài);5) F Q是是接受狀態(tài)集接受狀態(tài)集; 狀態(tài)圖等價(jià)于形式定義狀態(tài)圖等價(jià)于形式定義 Q=q1,q2,q3, 狀態(tài)集狀態(tài)集 =0,1, 字母表字母表 s=q1, 起始狀態(tài)起始狀態(tài) F=q2接受狀態(tài)集接受狀態(tài)集 01q1q1q2q2q3q2q3q2q2M1q1q2q3000,111圖靈對(duì)計(jì)算的觀察圖靈對(duì)計(jì)算的觀察圖靈圖靈: 計(jì)算通常是一個(gè)計(jì)算通常是一個(gè)人人拿著拿著筆筆在在紙紙上進(jìn)行的上進(jìn)行的. 他他根據(jù)根據(jù) 眼睛眼睛看到的紙上符號(hào)看到的紙上符號(hào), 腦腦中的若干中的若干法則

11、法則, 指示筆指示筆 在紙上在紙上擦掉或?qū)懮喜恋艋驅(qū)懮弦恍┓?hào)一些符號(hào), 再再改變他所看到的范圍改變他所看到的范圍. 繼續(xù)繼續(xù), 直到他認(rèn)為計(jì)算結(jié)束直到他認(rèn)為計(jì)算結(jié)束. 腦腦:控制器控制器 紙紙:存儲(chǔ)帶存儲(chǔ)帶 眼睛和筆眼睛和筆:讀寫頭讀寫頭 法則法則:轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)有限自動(dòng)機(jī)是簡(jiǎn)化的圖靈機(jī)有限自動(dòng)機(jī)是簡(jiǎn)化的圖靈機(jī)1101q1狀態(tài)狀態(tài): q1,q2,q3 起始狀態(tài)起始狀態(tài)q1 接受狀態(tài)接受狀態(tài)q2 轉(zhuǎn)移轉(zhuǎn)移: 箭頭箭頭運(yùn)行運(yùn)行: 從起始狀態(tài)開始沿轉(zhuǎn)移箭頭進(jìn)行從起始狀態(tài)開始沿轉(zhuǎn)移箭頭進(jìn)行.輸出輸出: 輸入讀完處于接受狀態(tài)則輸入讀完處于接受狀態(tài)則接受接受, 否則否則拒絕拒絕. 接受接受: 1, 1

12、1, 100, 101, 1101, 拒絕拒絕: , 0, 10, 110, 1010, M1是讀寫頭是讀寫頭不能改寫不能改寫, 且且只能右移只能右移的圖靈機(jī)的圖靈機(jī) q1q2q3000,111DFA計(jì)算計(jì)算的形式定義的形式定義設(shè)設(shè)M=(Q, , ,s,F)是一個(gè)是一個(gè)DFA,w=w1w2wn是字母表是字母表 上的一個(gè)字符串上的一個(gè)字符串.若若存在存在Q中中的狀態(tài)序列的狀態(tài)序列r0,r1,rn, 滿足滿足 1) r0 = s; 2) (ri, wi+1) = ri+1; 3) rn F則則M接受接受w.sw1r1w2r2rn-1wnrnq1q2q3000,111有限自動(dòng)機(jī)的語(yǔ)言有限自動(dòng)機(jī)的語(yǔ)言

13、:正則語(yǔ)言正則語(yǔ)言對(duì)有限自動(dòng)機(jī)對(duì)有限自動(dòng)機(jī)M, 若若 A = w* | M接受接受w , 即即A是有限自動(dòng)機(jī)是有限自動(dòng)機(jī)M的的語(yǔ)言語(yǔ)言, 記為記為L(zhǎng)(M)=A, 也也稱稱M識(shí)別識(shí)別A. 注注: M的語(yǔ)言唯一的語(yǔ)言唯一. M不識(shí)別任何其它語(yǔ)言不識(shí)別任何其它語(yǔ)言. 若存在若存在DFA識(shí)別語(yǔ)言識(shí)別語(yǔ)言A, 則稱則稱A是是正則語(yǔ)言正則語(yǔ)言. 稱兩個(gè)有限自動(dòng)機(jī)稱兩個(gè)有限自動(dòng)機(jī)等價(jià)等價(jià)若它們語(yǔ)言相同若它們語(yǔ)言相同. q1q2q3000,111M1注注: 在任何狀態(tài)在任何狀態(tài), 讀到讀到1后一定會(huì)進(jìn)入狀態(tài)后一定會(huì)進(jìn)入狀態(tài)q2. L(M1)=w | w是是0,1串串, 至少含一至少含一個(gè)個(gè)1, 且最后一個(gè)且最

14、后一個(gè)1后面含有偶數(shù)個(gè)后面含有偶數(shù)個(gè)0 注注: 任何其它語(yǔ)言都不是任何其它語(yǔ)言都不是M1的語(yǔ)言的語(yǔ)言.有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì)(難點(diǎn)難點(diǎn)) 自己即自動(dòng)機(jī)自己即自動(dòng)機(jī) 尋找需要記錄的尋找需要記錄的關(guān)鍵信息關(guān)鍵信息 設(shè)計(jì)識(shí)別下列語(yǔ)言的設(shè)計(jì)識(shí)別下列語(yǔ)言的DFA: w 0,1* | w從從1開始開始, 以以0結(jié)束結(jié)束 w 0,1* | w含有子串含有子串1010 w 0,1* | w的倒數(shù)第的倒數(shù)第2個(gè)符號(hào)是個(gè)符號(hào)是1 0k | k是是2或或3的倍數(shù)的倍數(shù) 有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) w 0,1* | w從從1開始開始, 以以0結(jié)束結(jié)束 =0,1, 根據(jù)根據(jù)關(guān)鍵信息設(shè)計(jì)狀態(tài)關(guān)鍵信息設(shè)計(jì)狀

15、態(tài), 空空, 以以0開始開始, 以以1開始開始以以0結(jié)束結(jié)束, 以以1開始開始以以1結(jié)束結(jié)束 空空0開始開始1開始開始0結(jié)束結(jié)束1開始開始1結(jié)束結(jié)束0 1 10 10 0,1 有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) w 0,1* | w含有子串含有子串1010 =0,1, 關(guān)鍵信息關(guān)鍵信息: , 1, 10, 101, 1010 0,1 1 0 1 1010101010 1 0 1 0 1 有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) w 0,1* | w倒數(shù)第倒數(shù)第2個(gè)符號(hào)是個(gè)符號(hào)是1 只需關(guān)注最后兩個(gè)符號(hào)只需關(guān)注最后兩個(gè)符號(hào) =0,1, 關(guān)鍵信息關(guān)鍵信息: , 0, 00, 1, 01, 10, 11 關(guān)鍵

16、信息改進(jìn)關(guān)鍵信息改進(jìn): , 1, 10, 111 0 0 1 10110 1 1 1 0 有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) 0k | k是是2或或3的倍數(shù)的倍數(shù) =0, 關(guān)鍵信息關(guān)鍵信息: ,01,02,03,04,05. 記為記為: 0,1,2,3,4,5100 0 0 240 0 30 5有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) 0k | k是是2或或3的倍數(shù)的倍數(shù) =0, 關(guān)鍵信息關(guān)鍵信息: ,01,02,03,04,05, 記記為為: 0,1,2,3,4,5 或或 (0,0), (1,1), (0,2), (1,0), (0,1), (1,2) 0k|k是是2或或3的倍數(shù)的倍數(shù) = 0k|k是

17、是2倍數(shù)倍數(shù) 0k|k是是3的倍數(shù)的倍數(shù) 0k|k是是2和和3的倍數(shù)的倍數(shù) = 0k|k是是2倍數(shù)倍數(shù) 0k|k是是3的倍數(shù)的倍數(shù)?(1,1)(0,0)0 0 0 (0,2)(0,1)0 0 (1,0)0 (1,2)100 0 100 0 20 有限自動(dòng)機(jī)的設(shè)計(jì)有限自動(dòng)機(jī)的設(shè)計(jì) 0k | k是是2和和3的倍數(shù)的倍數(shù) =0, 關(guān)鍵信息關(guān)鍵信息: ,01,02,03,04,05, 記記為為: 0,1,2,3,4,5 或或 (0,0), (1,1), (0,2), (1,0), (0,1), (1,2) 0k|k是是2和和3的倍數(shù)的倍數(shù) = 0k|k是是2倍數(shù)倍數(shù) 0k|k是是3的倍數(shù)的倍數(shù)(1,1

18、)(0,0)0 0 0 (0,2)(0,1)0 0 (1,0)0 (1,2)100 0 100 0 20 正則語(yǔ)言的并是正則語(yǔ)言正則語(yǔ)言的并是正則語(yǔ)言定理定理: 設(shè)設(shè)A,B都是都是 上的上的正則語(yǔ)言正則語(yǔ)言, 則則A B也是正則語(yǔ)言也是正則語(yǔ)言. 證明證明: 設(shè)設(shè)M1=(Q1, , 1,s1,F1)和和M2=(Q2, , 2,s2,F2)是是DFA, 且且 L(M1)=A, L(M2)=B, 令令Q=Q1 Q2, s=(s1,s2), F = F1 Q2 Q1 F2, : QQ, a, r1 Q1, r2 Q2, ( (r1,r2) , a ) = ( 1(r1,a), (r2,a) ), 即

19、對(duì)即對(duì)i=1,2, 第第i個(gè)分量按個(gè)分量按Mi的轉(zhuǎn)移函數(shù)變化的轉(zhuǎn)移函數(shù)變化. 令令M=(Q, , ,s,F), 則則 x ( x L(M) x A B ) 即即 L(M) = A B. 證畢證畢正則語(yǔ)言的交是正則語(yǔ)言正則語(yǔ)言的交是正則語(yǔ)言定理定理: 設(shè)設(shè)A,B都是都是 上的上的正則語(yǔ)言正則語(yǔ)言, 則則A B也是正則語(yǔ)言也是正則語(yǔ)言. 證明證明: 設(shè)設(shè)M1=(Q1, , 1,s1,F1)和和M2=(Q2, , 2,s2,F2)是是DFA, 且且 L(M1)=A, L(M2)=B, 令令Q=Q1 Q2, s=(s1,s2), F=F1 F2, : QQ, a, r1 Q1, r2 Q2, ( (r

20、1,r2) , a ) = ( 1(r1,a), (r2,a) ), 即對(duì)即對(duì)i=1,2, 第第i個(gè)分量按個(gè)分量按Mi的轉(zhuǎn)移函數(shù)變化的轉(zhuǎn)移函數(shù)變化. 令令M=(Q, , ,s,F), 則則 x ( x L(M) x A B ) 即即 L(M) = A B. 證畢證畢 證明特點(diǎn)證明特點(diǎn): 構(gòu)造性證明構(gòu)造性證明 正則語(yǔ)言與正則運(yùn)算正則語(yǔ)言與正則運(yùn)算如果語(yǔ)言如果語(yǔ)言A被一被一DFA識(shí)別識(shí)別,則稱則稱A是是正則語(yǔ)言正則語(yǔ)言算術(shù)中算術(shù)中, 對(duì)象是對(duì)象是數(shù)數(shù), 操作是操作是運(yùn)算運(yùn)算, 如如+ .計(jì)算理論中計(jì)算理論中, 對(duì)象是語(yǔ)言對(duì)象是語(yǔ)言, 操作是語(yǔ)言的運(yùn)算操作是語(yǔ)言的運(yùn)算.定義定義: 設(shè)設(shè)A和和B是兩個(gè)

21、語(yǔ)言是兩個(gè)語(yǔ)言,定義定義正則運(yùn)算正則運(yùn)算 并并,連接連接,星號(hào)星號(hào)如下如下: 并并: A B = x|x A或或x B 連接連接: A B = xy|x A且且y B 星號(hào)星號(hào): A* = x1x2xk|k 0且每個(gè)且每個(gè)xi A 正則運(yùn)算舉例正則運(yùn)算舉例設(shè)字母表設(shè)字母表 由由標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的2626個(gè)字母組成個(gè)字母組成A=good,bad, B=boy,girl, 則則A B= good, bad, boy, girl A B= goodboy, goodgirl, badboy, badgirl A*= , good, bad, goodgood, goodbad, 問(wèn)題問(wèn)題:1. 正則語(yǔ)言對(duì)

22、于正則運(yùn)算是否封閉正則語(yǔ)言對(duì)于正則運(yùn)算是否封閉? 2. 如何判斷一個(gè)語(yǔ)言是正則語(yǔ)言如何判斷一個(gè)語(yǔ)言是正則語(yǔ)言?非確定型機(jī)器非確定型機(jī)器(難點(diǎn)難點(diǎn))前面因?yàn)榍懊嬉驗(yàn)?: Q Q是一個(gè)函數(shù)是一個(gè)函數(shù), 所以所以 每步存在唯一的方式進(jìn)入下一狀態(tài)每步存在唯一的方式進(jìn)入下一狀態(tài) 稱為稱為確定型確定型有限自動(dòng)機(jī)有限自動(dòng)機(jī)(DFA) 現(xiàn)在引入現(xiàn)在引入非確定型非確定型有限自動(dòng)機(jī)有限自動(dòng)機(jī)(NFA) q1q2q3q40,110,10,1 每步可以每步可以0至多種方式進(jìn)入下一步至多種方式進(jìn)入下一步 轉(zhuǎn)移箭頭上的符號(hào)可以是空串轉(zhuǎn)移箭頭上的符號(hào)可以是空串 , 表示不讀任何輸入就可以轉(zhuǎn)移過(guò)去表示不讀任何輸入就可以轉(zhuǎn)移過(guò)

23、去 非確定型計(jì)算非確定型計(jì)算q1q2q3q40,110,10,1輸入輸入01011q1q101q2q1q30q1q31q3q2q1q4q3q2q1q41注注: 若起始狀態(tài)有射出的若起始狀態(tài)有射出的 箭頭箭頭? NFA的計(jì)算方式的計(jì)算方式Step 1.設(shè)讀到符號(hào)設(shè)讀到符號(hào)s, 對(duì)對(duì)(每個(gè)副本每個(gè)副本)機(jī)器狀態(tài)機(jī)器狀態(tài)q, 若若q有多個(gè)射出有多個(gè)射出s箭頭箭頭,則機(jī)器分裂成多個(gè)副本則機(jī)器分裂成多個(gè)副本. 狀態(tài)相同的副本視為同一副本狀態(tài)相同的副本視為同一副本.Step 2. 對(duì)每個(gè)副本的狀態(tài)對(duì)每個(gè)副本的狀態(tài),若其上有射出的若其上有射出的 箭頭箭頭, 則不讀任何輸入則不讀任何輸入, 機(jī)器分裂出相應(yīng)副本

24、機(jī)器分裂出相應(yīng)副本.Step 3. 讀下一個(gè)輸入符號(hào)讀下一個(gè)輸入符號(hào), 轉(zhuǎn)轉(zhuǎn)step1. 若無(wú)輸入符號(hào)若無(wú)輸入符號(hào), 計(jì)算結(jié)束計(jì)算結(jié)束, 并且并且, 若此時(shí)有一個(gè)副本處于接受狀態(tài)若此時(shí)有一個(gè)副本處于接受狀態(tài),則接受則接受, 否則拒絕否則拒絕.NFA的形式定義的形式定義定義定義: NFA是一個(gè)是一個(gè)5元組元組(Q, , ,s,F),1) Q是是狀態(tài)集狀態(tài)集;2) 是字母表是字母表;3) : Q P(Q)是轉(zhuǎn)移函數(shù)是轉(zhuǎn)移函數(shù);4) s Q是是起始狀態(tài)起始狀態(tài);5) F Q是是接受狀態(tài)集接受狀態(tài)集; 其中其中 = 狀態(tài)圖狀態(tài)圖與與 形式定義形式定義 包含包含相同信息相同信息q1q2q3q40,110

25、,10,1試寫出該狀態(tài)圖試寫出該狀態(tài)圖 對(duì)應(yīng)的形式定義對(duì)應(yīng)的形式定義 (q1,1) (q2, ) (q2,1) (q1, )= q1,q2 = q3 = = 如何定義如何定義NFA的計(jì)算的計(jì)算q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA計(jì)算的形式定義計(jì)算的形式定義設(shè)設(shè)N=(Q, , ,q0,F)是一臺(tái)是一臺(tái)NFA, w是是 上字符串上字符串 稱稱 N接受接受w, 若若 w能寫作能寫作w=w1w2wn, wi ,且且 存在存在Q中的狀態(tài)序列中的狀態(tài)序列r0,r1,rn, 滿足滿足 1) r0 = q0; 2) ri+1(ri,

26、 wi+1); 3) rn Fr0w1r1w2r2rn-1wnrn對(duì)于輸入對(duì)于輸入, NFA計(jì)算的路徑可能不唯一計(jì)算的路徑可能不唯一.NFA計(jì)算形式定義舉例計(jì)算形式定義舉例q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA的設(shè)計(jì)的設(shè)計(jì)(難點(diǎn)難點(diǎn)) 自己即自動(dòng)機(jī)自己即自動(dòng)機(jī) 尋找需要記錄的關(guān)鍵信息尋找需要記錄的關(guān)鍵信息 設(shè)計(jì)識(shí)別設(shè)計(jì)識(shí)別0,1上以下語(yǔ)言的上以下語(yǔ)言的NFA: w 0,1* | w從從1開始開始, 以以0結(jié)束結(jié)束 w 0,1* | w含有子串含有子串1010 w 0,1* | w是倒數(shù)第是倒數(shù)第2位是位是1 0k |

27、k是是2或或3的倍數(shù)的倍數(shù) NFA的設(shè)計(jì)的設(shè)計(jì) w 0,1* | w從從1開始開始, 以以0結(jié)束結(jié)束 =0,1, 根據(jù)根據(jù)關(guān)鍵信息設(shè)計(jì)狀態(tài)關(guān)鍵信息設(shè)計(jì)狀態(tài), 空空, 以以0開始開始, 以以1開始開始以以1結(jié)束結(jié)束, 以以1開始以開始以0結(jié)束結(jié)束 0 空空0開始開始 1開始開始0結(jié)束結(jié)束 1開始開始1結(jié)束結(jié)束 0 1 10 10,1 DFA 空空1開始開始 0結(jié)束結(jié)束1開始開始 0,1 0 1NFA NFA的設(shè)計(jì)的設(shè)計(jì) w 0,1* | w含有子串含有子串1010 =0,1, 關(guān)鍵信息關(guān)鍵信息: 忽略忽略( ), 1, 10, 101, 1010 0,1 1 1 0 0 1010100 1 0

28、1011 1 DFA 1忽略忽略 1 0 0,1 1010100 0,1 1011 NFA NFA的設(shè)計(jì)的設(shè)計(jì) w 0,1* | w倒數(shù)第倒數(shù)第2個(gè)符號(hào)是個(gè)符號(hào)是1 =0,1, 關(guān)鍵信息關(guān)鍵信息: 忽略忽略( ), 1, 1x, 1 1 0 0 10110 1 1 1 0 DFA 1忽略忽略 1 0,1 0,1 1xNFA NFA與與DFA等價(jià)等價(jià)定理定理: 每個(gè)每個(gè)NFA都有一臺(tái)等價(jià)的都有一臺(tái)等價(jià)的DFA.q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1N構(gòu)造構(gòu)造DFA 關(guān)鍵關(guān)鍵信息信息 每個(gè)時(shí)刻每個(gè)時(shí)刻 所有所有副本狀態(tài)副本狀態(tài)的集

29、合的集合每個(gè)每個(gè)NFA都有等價(jià)的都有等價(jià)的DFAq1q2q3q40,110,10,1編號(hào)編號(hào) 011q1q1q1, q2, q322q1, q2, q3q1, q33q1, q2, q3, q443q1, q3q1q1, q2, q3, q44*q1, q2, q3, q4q1, q3, q45q1, q2, q3, q45*q1, q3, q4q1, q46q1, q2, q3, q46*q1, q4q1, q4q1, q2, q3, q4以原狀態(tài)的子集以原狀態(tài)的子集 為新機(jī)器的狀態(tài)為新機(jī)器的狀態(tài) 每個(gè)每個(gè)NFA都有等價(jià)的都有等價(jià)的DFA證明證明: 設(shè)設(shè)N = (Q1, , 1,s1,F1)

30、是是NFA, /設(shè)計(jì)設(shè)計(jì)Q,F, s, 令令 Q = P(Q1), /全體子集全體子集 F = A Q : F1 A , s = E(s1), E(A) = q : r A, r經(jīng)經(jīng)0到多個(gè)到多個(gè) 箭頭可達(dá)箭頭可達(dá)q : QQ, a, A Q, ( A, a ) = E( r A 1(r,a) ) M = (Q, , ,s,F), 則則 x ( x L(M) x L(N) ), 即即 L(M) = L(N). 證證畢畢 q1q2q3q40,110,10,1正則運(yùn)算的封閉性正則運(yùn)算的封閉性定理定理: 正則語(yǔ)言對(duì)正則語(yǔ)言對(duì)并并運(yùn)算封閉運(yùn)算封閉.定理定理: 正則語(yǔ)言對(duì)正則語(yǔ)言對(duì)連接連接運(yùn)算封閉運(yùn)算封

31、閉. 定理定理: 正則語(yǔ)言對(duì)正則語(yǔ)言對(duì)星號(hào)星號(hào)運(yùn)算封閉運(yùn)算封閉. 證明證明: 畫狀態(tài)圖畫狀態(tài)圖.證明若證明若A, B正則正則, 則則A B正則正則DFA: M1=(Q1, , 1,s1,F1), M2=(Q2, , 2,s2,F2), L(M1)=A, L(M2)=B, 令令 Q = Q1 Q2 s 不不交并交并, F = F1 F2 不交并不交并 i=1,2, r Qi, a, (r,a) = i(r,a) (s, ) = s1,s2 M=(Q, , ,s,F), 則則 L(M) = A B. M1 s1M2 s2M1 M2 s M s1s2證明若證明若A, B正則正則, 則則A B正則正則

32、DFA: M1=(Q1, , 1,s1,F1), M2=(Q2, , 2,s2,F2), L(M1)=A, L(M2)=B, 令令 Q = Q1 Q2 不不交并交并, F = F2 , r F1, (r, ) = s2 i=1,2, r Qi, a, (r,a) = i(r,a) M=(Q, , ,s1,F), 則則 L(M) = A B. M1 s1M2 s2M1 M2 M s1s2證明若證明若A正則正則, 則則A*正則正則DFA: M1=(Q1, , 1,s1,F1), L(M1)=A, 令令 Q = Q1 s 不不交并交并, F = F1 s 不交并不交并 r Q1, a, (r,a)

33、= 1(r,a) r F1, (r, ) = s1, (s, ) = s1, M=(Q, , ,s,F), 則則 L(M) = A*. M1 s1M1 s1s M 正則表達(dá)式正則表達(dá)式定義定義: 稱稱R是一個(gè)正則表達(dá)式是一個(gè)正則表達(dá)式, 若若R是是 1) a, a ; 2) ; 3) ; 4) (R1 R2), R1和和R2是正則表達(dá)式是正則表達(dá)式; 5) (R1 R2), R1和和R2是正則表達(dá)式是正則表達(dá)式; 6) (R1*), R1是正則表達(dá)式是正則表達(dá)式;每個(gè)正則表達(dá)式每個(gè)正則表達(dá)式R表示一個(gè)語(yǔ)言表示一個(gè)語(yǔ)言(?),記為記為L(zhǎng)(R).例例: 0*10*, 01 10, ()*, 1*,

34、 *.正則表達(dá)式與正則表達(dá)式與DFA等價(jià)等價(jià)定理定理2.3.1: 語(yǔ)言語(yǔ)言A正則正則A可用正則表達(dá)式描述可用正則表達(dá)式描述. () 若若 語(yǔ)言語(yǔ)言A可用正則表達(dá)式描述可用正則表達(dá)式描述, 則則 A正則正則. (容易容易)() 若語(yǔ)言若語(yǔ)言A正則正則, 則則A可用正則表達(dá)式描述可用正則表達(dá)式描述. (困難困難)A有正則表達(dá)式有正則表達(dá)式A正則正則數(shù)學(xué)歸納法數(shù)學(xué)歸納法 R是一個(gè)正則表達(dá)式是一個(gè)正則表達(dá)式, 若若R是是 1) a, a 2) 3) 4) (R1 R2) 5) (R1 R2) 6) (R1*)aA正則正則A有正則表達(dá)式有正則表達(dá)式構(gòu)造廣義非確定有限自動(dòng)機(jī)構(gòu)造廣義非確定有限自動(dòng)機(jī)(GNF

35、A) 非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī) 轉(zhuǎn)移箭頭可以用任何正則表達(dá)式作標(biāo)號(hào)轉(zhuǎn)移箭頭可以用任何正則表達(dá)式作標(biāo)號(hào) 證明中的特殊要求證明中的特殊要求: 起始狀態(tài)無(wú)射入箭頭起始狀態(tài)無(wú)射入箭頭. 唯一接受狀態(tài)唯一接受狀態(tài)(無(wú)射出箭頭無(wú)射出箭頭).手段手段: 一個(gè)一個(gè)地去掉中間狀態(tài)一個(gè)一個(gè)地去掉中間狀態(tài).刪除一個(gè)中間狀態(tài)刪除一個(gè)中間狀態(tài)設(shè)設(shè)qrip為待刪中間狀態(tài)為待刪中間狀態(tài), 對(duì)任意兩個(gè)狀態(tài)對(duì)任意兩個(gè)狀態(tài)qi, qj都需要修改箭頭標(biāo)號(hào)都需要修改箭頭標(biāo)號(hào) qiqjqripR4 R2 R1 R3 qiqj(R1)(R2)*(R3)(R4) 舉例舉例: A正則正則A有正則表達(dá)式有正則表達(dá)式123a a a b

36、 b b 123a a a b b b sac 添起始狀態(tài)添起始狀態(tài)s(無(wú)無(wú)進(jìn)入箭頭進(jìn)入箭頭), 接受狀態(tài)接受狀態(tài)ac(無(wú)射無(wú)射出箭頭出箭頭), 改掉其它接受狀態(tài)改掉其它接受狀態(tài) s23a ba a ab bb b aa b ac 刪狀態(tài)刪狀態(tài)1 s3a(aa b)* (ba a)(aa b)* (ba a)(aa b)*ab bb a(aa b)*ab b ac刪除狀態(tài)刪除狀態(tài)2 s( (a(aa b)*ab b)(ba a)(aa b)*ab bb)* (ba a)(aa b)*) ) ( a(aa b)*)ac刪除狀態(tài)刪除狀態(tài)3 非正則語(yǔ)言非正則語(yǔ)言B= 0n1n | n 0 C= w

37、| w中中0和和1的個(gè)數(shù)相等的個(gè)數(shù)相等 D= w | w中中01和和10的個(gè)數(shù)相等的個(gè)數(shù)相等 哪些是哪些是正則語(yǔ)言正則語(yǔ)言?泵引理的等價(jià)描述泵引理的等價(jià)描述定理定理(泵引理泵引理): 設(shè)設(shè)A是正則語(yǔ)言是正則語(yǔ)言,則則存在存在p0使得使得 對(duì)對(duì)任意任意w A, |w| p, 存在存在分割分割w=xyz滿足滿足 1) 對(duì)對(duì)任意任意 i 0, xyiz A; 2) |y|0; 3) |xy| p. 若若A是正則是正則語(yǔ)言語(yǔ)言, 則則 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A.若若 p0 w A(|w| p) x,y,z(|y|0, |x

38、y| p, w=xyz) i 0, xyiz A. 則則A非非正則語(yǔ)言正則語(yǔ)言 B = 0n1n | n 0 非正則非正則 p0, 令令w=0p1p, x,y,z(|y|0, |xy| p, w=xyz) 令令i=0, xz = 0p-|y|1p B B非非正則語(yǔ)言正則語(yǔ)言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 則則A非非正則語(yǔ)言正則語(yǔ)言 C = ww | w 0,1* 非正則非正則 p0, 令令w=0p10p1, x,y,z(|y|0, |xy| p, w=xyz) 令令i=0, xz = 0p-|y|10p1 C

39、C非非正則語(yǔ)言正則語(yǔ)言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 則則A非非正則語(yǔ)言正則語(yǔ)言 D = 1k | k=2n, n 0 非正則非正則 p0, 令令w=1k, k=2p+1, x,y,z(|y|0, |xy| p, w=xyz) 令令i=2, 2p+1|xy2z|=k+|y|0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 則則A非非正則語(yǔ)言正則語(yǔ)言泵引理的證明泵引理的證明定理定理(泵引理泵引理): 設(shè)設(shè)A是正則語(yǔ)言是正則語(yǔ)言,則則存在存在p0使得使得 對(duì)對(duì)

40、任意任意w A, |w| p, 存在存在分割分割w=xyz滿足滿足 1) 對(duì)對(duì)任意任意 k 0, xykz A; 2) |y|0; 3) |xy| p. 證明證明: 令令M=(Q, , ,s,F) 且且 L(M)=A, 令令p=|Q|, 設(shè)設(shè) w = w1w2wn A, wi, 且且n p, 則有則有 s=r0w1r1w2r2rn-1wnrn F 由鴿巢原理由鴿巢原理, 存在存在ij p使得使得ri=rj, 令令x=w1wi, y=wi+1wj, z=wj+1wn. 那么對(duì)那么對(duì) k 0, xykz A. 本章作業(yè)本章作業(yè)1.1 下圖給出了兩臺(tái)下圖給出了兩臺(tái)DFA M1和和M2的狀態(tài)圖。的狀態(tài)

41、圖。 回答下述關(guān)于這兩臺(tái)機(jī)器的問(wèn)題?；卮鹣率鲫P(guān)于這兩臺(tái)機(jī)器的問(wèn)題。 a. 它們的起始狀態(tài)是什么它們的起始狀態(tài)是什么? b. 它們的接受狀態(tài)集是什么它們的接受狀態(tài)集是什么? c. 對(duì)輸入對(duì)輸入aabb，它們經(jīng)過(guò)的狀態(tài)序列是什么，它們經(jīng)過(guò)的狀態(tài)序列是什么? d. 它們接受字符串它們接受字符串a(chǎn)abb嗎嗎? e.它們接受它們接受字符串字符串 嗎嗎? 1.6 畫出識(shí)別下述語(yǔ)言的畫出識(shí)別下述語(yǔ)言的DFA狀態(tài)圖。字母表為狀態(tài)圖。字母表為0,1 d. w | w的長(zhǎng)度不小于的長(zhǎng)度不小于3, 并且第并且第3個(gè)符號(hào)為個(gè)符號(hào)為0;1.7. 給出下述語(yǔ)言的給出下述語(yǔ)言的NFA，并且符合規(guī)定的狀態(tài)數(shù)。，并且符合規(guī)定的

42、狀態(tài)數(shù)。 字母表為字母表為0,1 e. 語(yǔ)言語(yǔ)言0*1*0*0, 3個(gè)狀態(tài)。個(gè)狀態(tài)。1.29 使用泵引理證明下述語(yǔ)言不是正則的。使用泵引理證明下述語(yǔ)言不是正則的。 b. A = www | w a,b* 第第4章章 圖靈機(jī)圖靈機(jī)1. 圖靈機(jī)基礎(chǔ)圖靈機(jī)基礎(chǔ)1.1 圖靈機(jī)的定義圖靈機(jī)的定義1.2 圖靈機(jī)舉例圖靈機(jī)舉例1.3 圖靈機(jī)的描述圖靈機(jī)的描述圖靈對(duì)計(jì)算的觀察圖靈對(duì)計(jì)算的觀察圖靈圖靈: 計(jì)算通常是一個(gè)計(jì)算通常是一個(gè)人人拿著拿著筆筆在在紙紙上進(jìn)行的上進(jìn)行的. 他他根據(jù)根據(jù) 眼睛眼睛看到的紙上符號(hào)看到的紙上符號(hào), 腦腦中的若干中的若干法則法則, 指示筆指示筆 在紙上在紙上擦掉或?qū)懮喜恋艋驅(qū)懮弦恍┓?/p>

43、號(hào)一些符號(hào), 再再改變他所看到的范圍改變他所看到的范圍. 繼續(xù)繼續(xù), 直到他認(rèn)為計(jì)算結(jié)束直到他認(rèn)為計(jì)算結(jié)束. 腦腦:控制器控制器 紙紙:存儲(chǔ)帶存儲(chǔ)帶 眼睛和筆眼睛和筆:讀寫頭讀寫頭 法則法則:轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)與有限自動(dòng)機(jī)的區(qū)別與有限自動(dòng)機(jī)的區(qū)別有限自動(dòng)機(jī)有限自動(dòng)機(jī): 輸入帶長(zhǎng)度有限輸入帶長(zhǎng)度有限 只能只能讀讀和和右移右移, 不能不能寫寫和和左移左移 讀完輸入停機(jī)讀完輸入停機(jī)圖靈機(jī)圖靈機(jī)(TM)的形式化定義的形式化定義TM是一個(gè)是一個(gè)7元組元組(Q, , , , q0, qa, qr)1) Q是是狀態(tài)集狀態(tài)集.2) 是是輸入字母表輸入字母表,不包括空白符不包括空白符.3) 是是帶字母表帶字母表,

44、其中其中, .4) : QQL,R是是轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù).5) q0 Q是是起始起始狀態(tài)狀態(tài). 6) qa Q是是接受接受狀態(tài)狀態(tài). 7) qr Q是是拒絕拒絕狀態(tài)狀態(tài), qa qr .圖靈機(jī)的初始化圖靈機(jī)的初始化設(shè)設(shè)M=(Q, , , , q0, qa, qr), w=w1wnn, 輸入帶輸入帶: 將輸入串將輸入串w放在最左端放在最左端n格中格中, 帶子其余部分補(bǔ)充空格帶子其余部分補(bǔ)充空格. 讀寫頭讀寫頭: 指向工作帶最左端指向工作帶最左端.例例:設(shè)輸入串為設(shè)輸入串為0101, 則其初始形態(tài)為則其初始形態(tài)為圖靈機(jī)的運(yùn)行圖靈機(jī)的運(yùn)行 圖靈機(jī)根據(jù)轉(zhuǎn)移函數(shù)運(yùn)行圖靈機(jī)根據(jù)轉(zhuǎn)移函數(shù)運(yùn)行. 例例:設(shè)輸入串

45、為設(shè)輸入串為0101, 且且 (q0,0)=( p,#,R), 則有則有 注注: 若要在最左端左移若要在最左端左移, 讀寫頭保持不動(dòng)讀寫頭保持不動(dòng). (q0,0)=( p,#,R)的狀態(tài)圖表示的狀態(tài)圖表示:簡(jiǎn)記為簡(jiǎn)記為判定器與語(yǔ)言分類判定器與語(yǔ)言分類 圖靈機(jī)運(yùn)行的三種結(jié)果圖靈機(jī)運(yùn)行的三種結(jié)果 1. 若若TM進(jìn)入進(jìn)入接受狀態(tài)接受狀態(tài),則停機(jī)且接受輸入則停機(jī)且接受輸入, 2. 若若TM進(jìn)入進(jìn)入拒絕狀態(tài)拒絕狀態(tài),則停機(jī)且拒絕輸入則停機(jī)且拒絕輸入, 3. 否則否則TM一直運(yùn)行一直運(yùn)行,不停機(jī)不停機(jī). 定義定義: 稱圖靈機(jī)稱圖靈機(jī)M為為判定器判定器, 若若M對(duì)所有輸入都停機(jī)對(duì)所有輸入都停機(jī). 定義不同語(yǔ)

46、言類定義不同語(yǔ)言類: 圖靈圖靈可判定可判定語(yǔ)言語(yǔ)言: 某個(gè)判定器的語(yǔ)言某個(gè)判定器的語(yǔ)言(也稱也稱遞歸語(yǔ)言遞歸語(yǔ)言) 圖靈圖靈可識(shí)別可識(shí)別語(yǔ)言語(yǔ)言: 某個(gè)圖靈機(jī)的語(yǔ)言某個(gè)圖靈機(jī)的語(yǔ)言, 也稱為也稱為遞歸可枚舉語(yǔ)言遞歸可枚舉語(yǔ)言 q1 q2 0L 1#, R 圖靈機(jī)的格局圖靈機(jī)的格局 描述圖靈機(jī)運(yùn)行的每一步需要如下信息描述圖靈機(jī)運(yùn)行的每一步需要如下信息: 控制器的控制器的狀態(tài)狀態(tài); 存儲(chǔ)帶上存儲(chǔ)帶上字符串字符串; 讀寫頭的讀寫頭的位置位置. 定義定義: 對(duì)于圖靈機(jī)對(duì)于圖靈機(jī)M=(Q, , , , q0, qa, qr), 設(shè)設(shè)q Q, u,v*, 則則格局格局 uqv 表示表示 1) 當(dāng)前控制器當(dāng)

47、前控制器狀態(tài)狀態(tài)為為q ; 2) 存儲(chǔ)帶存儲(chǔ)帶上字符串為上字符串為uv(其余為空格其余為空格); 3) 讀寫頭讀寫頭指向指向v的第一個(gè)符號(hào)的第一個(gè)符號(hào). 起始格局起始格局, 接受格局接受格局, 拒絕格局拒絕格局.q0 qa 0L 1R q0 qa 0L 1R qr |_|R 格局演化舉例格局演化舉例 s qa 0L 1R qr |_|R s 0 1 s 0 1 循環(huán)循環(huán) s 1 0 1 qa 0 接受接受 s _ _ _ qr _ 拒絕拒絕 圖靈機(jī)計(jì)算的形式定義圖靈機(jī)計(jì)算的形式定義稱圖靈機(jī)稱圖靈機(jī)M接受接受字符串字符串w,若存在格局序列若存在格局序列C1,C2,Ck使得使得 1) C1是是M的

48、起始格局的起始格局q0w; 2) Ci產(chǎn)生產(chǎn)生Ci+1, i=1,k-1; 3) Ck是是M的接受格局的接受格局. M的的語(yǔ)言語(yǔ)言: M接受的所有字符串的集合接受的所有字符串的集合, 記為記為L(zhǎng)(M).1. 圖靈機(jī)基礎(chǔ)圖靈機(jī)基礎(chǔ)1.1 圖靈機(jī)的定義圖靈機(jī)的定義1.2 圖靈機(jī)舉例圖靈機(jī)舉例1.3 圖靈機(jī)的描述圖靈機(jī)的描述圖靈機(jī)舉例圖靈機(jī)舉例 =0,1, A=0w1 : w* 正則語(yǔ)言正則語(yǔ)言 B=0n1n : n 0 上下文無(wú)關(guān)語(yǔ)言上下文無(wú)關(guān)語(yǔ)言 =0, C=0k:k=2n,n 0 圖靈圖靈可判定可判定語(yǔ)言語(yǔ)言 M=“對(duì)于輸入串對(duì)于輸入串w, 1) 若若w= , 則拒絕則拒絕. 2) 若只有若只

49、有1個(gè)個(gè)0,則接受則接受. 3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕. 4) 隔一個(gè)隔一個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2).”L(M)=C, 即即M識(shí)別識(shí)別C.狀態(tài)圖狀態(tài)圖M=“對(duì)于輸入對(duì)于輸入w,1) 若若w= , 則拒絕則拒絕.2) 若只有若只有1個(gè)個(gè)0,則接受則接受.3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕.4) 隔一個(gè)隔一個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2).”Rqrq0狀態(tài)圖狀態(tài)圖q0Rqrq10$,RRqaq20 x,RM=“對(duì)于輸入對(duì)于輸入w,1) 若若w= , 則拒絕則拒絕.2) 若只有若只有1個(gè)個(gè)0,則接受則接受.3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕.4) 隔一個(gè)隔一

50、個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2).”狀態(tài)圖狀態(tài)圖q0Rqrq10$,RRqaq20 x,Rq30R0 x,RRM=“對(duì)于輸入對(duì)于輸入w,1) 若若w= , 則拒絕則拒絕.2) 若只有若只有1個(gè)個(gè)0,則接受則接受.3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕.4) 隔一個(gè)隔一個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2).”狀態(tài)圖狀態(tài)圖q0Rqrq10$,RRqaq20 x,Rq30R0 x,RRq4L0LxL $RM=“對(duì)于輸入對(duì)于輸入w,1) 若若w= , 則拒絕則拒絕.2) 若只有若只有1個(gè)個(gè)0,則接受則接受.3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕.4) 隔一個(gè)隔一個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2

51、).”狀態(tài)圖狀態(tài)圖q30R0 x,RRq0Rqrq10$,RRqaq20 x,Rq4L0LxL$RxRxRxRM=“對(duì)于輸入對(duì)于輸入w,1) 若若w= , 則拒絕則拒絕.2) 若只有若只有1個(gè)個(gè)0,則接受則接受.3) 若有奇數(shù)個(gè)若有奇數(shù)個(gè)0,則拒絕則拒絕.4) 隔一個(gè)隔一個(gè)0,刪一個(gè)刪一個(gè)0. 轉(zhuǎn)轉(zhuǎn)(2).”各種語(yǔ)言類的包含關(guān)系各種語(yǔ)言類的包含關(guān)系正則語(yǔ)言正則語(yǔ)言 上下文無(wú)關(guān)語(yǔ)言上下文無(wú)關(guān)語(yǔ)言 可判定語(yǔ)言可判定語(yǔ)言 圖靈可識(shí)別語(yǔ)言圖靈可識(shí)別語(yǔ)言 P( *)?圖靈機(jī)的描述圖靈機(jī)的描述(1) 形式水平的描述形式水平的描述(狀態(tài)圖或轉(zhuǎn)移函數(shù)狀態(tài)圖或轉(zhuǎn)移函數(shù))(2) 實(shí)現(xiàn)水平的描述實(shí)現(xiàn)水平的描述(讀寫頭的移動(dòng)讀寫頭的移動(dòng),改寫改寫)(3) 高水平描述高水平描述(使用日常語(yǔ)言使用日常語(yǔ)言)用帶引號(hào)的文字段來(lái)表示圖靈機(jī)用帶引號(hào)的文