計算理論_計算模型CH1_2016new

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

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

3、y. O(n-m+1)m) 觀察改進方法觀察改進方法 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 構造狀態(tài)和轉(zhuǎn)移函數(shù)構造狀態(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, 串匹配的有限自動機算法串匹配的有限自動機算法符號集符號集 , m=Length(y), 計算計算轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù), Yi=y1y2yi. 1. 對對 q = 0:m 2. 對每個符號對每個符號a , 3. k=minm,q+1 4. 當當 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. 對對 i = 1:n 3. q=f(q,xi), 4. 若若q=m, 打印打印 i-m+1 字符串匹配算法字符串匹配算法算法算法預處理時間預處理時間匹配時間匹配時間樸素樸素0O(n-m+1)m)自動機自動機O(m| |) (n)Knuth-Morris-Pratt (m) (n)其中其中 是字母表是字母表 字符串與語言字符串與語言字母表字母表: 任意一個有限集任意一個有限集. 常用記號常用記

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

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

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

9、否是2的冪次的冪次”- 02n : n 0 “圖是否連通圖是否連通”- | G是連通圖是連通圖 其中其中是圖是圖G編碼成的字符串編碼成的字符串.給定有限字母表給定有限字母表 , 每個輸入是一個串每個輸入是一個串, 任意串都可以是輸入串任意串都可以是輸入串 一個決定性問題是滿足某性質(zhì)的串的集合一個決定性問題是滿足某性質(zhì)的串的集合(語言語言) 當機器從簡單到復雜當機器從簡單到復雜, 能解決的問題也變復雜能解決的問題也變復雜確定型有限確定型有限(窮窮)自動機的形式定義自動機的形式定義定義定義: 有限自動機有限自動機是一個是一個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)圖等價于形式定義狀態(tài)圖等價于形式定義 Q=q1,q2,q3, 狀態(tài)集狀態(tài)集 =0,1, 字母表字母表 s=q1, 起始狀態(tài)起始狀態(tài) F=q2接受狀態(tài)集接受狀態(tài)集 01q1q1q2q2q3q2q3q2q2M1q1q2q3000,111圖靈對計算的觀察圖靈對計算的觀察圖靈圖靈: 計算通常是一個計算通常是一個人人拿著拿著筆筆在在紙紙上進行的上進行的. 他他根據(jù)根據(jù) 眼睛眼睛看到的紙上符號看到的紙上符號, 腦腦中的若干中的若干法則

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

12、1, 100, 101, 1101, 拒絕拒絕: , 0, 10, 110, 1010, M1是讀寫頭是讀寫頭不能改寫不能改寫, 且且只能右移只能右移的圖靈機的圖靈機 q1q2q3000,111DFA計算計算的形式定義的形式定義設設M=(Q, , ,s,F)是一個是一個DFA,w=w1w2wn是字母表是字母表 上的一個字符串上的一個字符串.若若存在存在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有限自動機的語言有限自動機的語言

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

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

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 有限自動機的設計有限自動機的設計 w 0,1* | w含有子串含有子串1010 =0,1, 關鍵信息關鍵信息: , 1, 10, 101, 1010 0,1 1 0 1 1010101010 1 0 1 0 1 有限自動機的設計有限自動機的設計 w 0,1* | w倒數(shù)第倒數(shù)第2個符號是個符號是1 只需關注最后兩個符號只需關注最后兩個符號 =0,1, 關鍵信息關鍵信息: , 0, 00, 1, 01, 10, 11 關鍵

16、信息改進關鍵信息改進: , 1, 10, 111 0 0 1 10110 1 1 1 0 有限自動機的設計有限自動機的設計 0k | k是是2或或3的倍數(shù)的倍數(shù) =0, 關鍵信息關鍵信息: ,01,02,03,04,05. 記為記為: 0,1,2,3,4,5100 0 0 240 0 30 5有限自動機的設計有限自動機的設計 0k | k是是2或或3的倍數(shù)的倍數(shù) =0, 關鍵信息關鍵信息: ,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 有限自動機的設計有限自動機的設計 0k | k是是2和和3的倍數(shù)的倍數(shù) =0, 關鍵信息關鍵信息: ,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 正則語言的并是正則語言正則語言的并是正則語言定理定理: 設設A,B都是都是 上的上的正則語言正則語言, 則則A B也是正則語言也是正則語言. 證明證明: 設設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、對即對i=1,2, 第第i個分量按個分量按Mi的轉(zhuǎn)移函數(shù)變化的轉(zhuǎn)移函數(shù)變化. 令令M=(Q, , ,s,F), 則則 x ( x L(M) x A B ) 即即 L(M) = A B. 證畢證畢正則語言的交是正則語言正則語言的交是正則語言定理定理: 設設A,B都是都是 上的上的正則語言正則語言, 則則A B也是正則語言也是正則語言. 證明證明: 設設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) ), 即對即對i=1,2, 第第i個分量按個分量按Mi的轉(zhuǎn)移函數(shù)變化的轉(zhuǎn)移函數(shù)變化. 令令M=(Q, , ,s,F), 則則 x ( x L(M) x A B ) 即即 L(M) = A B. 證畢證畢 證明特點證明特點: 構造性證明構造性證明 正則語言與正則運算正則語言與正則運算如果語言如果語言A被一被一DFA識別識別,則稱則稱A是是正則語言正則語言算術中算術中, 對象是對象是數(shù)數(shù), 操作是操作是運算運算, 如如+ .計算理論中計算理論中, 對象是語言對象是語言, 操作是語言的運算操作是語言的運算.定義定義: 設設A和和B是兩個

21、語言是兩個語言,定義定義正則運算正則運算 并并,連接連接,星號星號如下如下: 并并: A B = x|x A或或x B 連接連接: A B = xy|x A且且y B 星號星號: A* = x1x2xk|k 0且每個且每個xi A 正則運算舉例正則運算舉例設字母表設字母表 由由標準的標準的2626個字母組成個字母組成A=good,bad, B=boy,girl, 則則A B= good, bad, boy, girl A B= goodboy, goodgirl, badboy, badgirl A*= , good, bad, goodgood, goodbad, 問題問題:1. 正則語言對

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

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

24、機器分裂出相應副本.Step 3. 讀下一個輸入符號讀下一個輸入符號, 轉(zhuǎn)轉(zhuǎn)step1. 若無輸入符號若無輸入符號, 計算結(jié)束計算結(jié)束, 并且并且, 若此時有一個副本處于接受狀態(tài)若此時有一個副本處于接受狀態(tài),則接受則接受, 否則拒絕否則拒絕.NFA的形式定義的形式定義定義定義: NFA是一個是一個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)圖 對應的形式定義對應的形式定義 (q1,1) (q2, ) (q2,1) (q1, )= q1,q2 = q3 = = 如何定義如何定義NFA的計算的計算q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA計算的形式定義計算的形式定義設設N=(Q, , ,q0,F)是一臺是一臺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對于輸入對于輸入, NFA計算的路徑可能不唯一計算的路徑可能不唯一.NFA計算形式定義舉例計算形式定義舉例q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1NNFA的設計的設計(難點難點) 自己即自動機自己即自動機 尋找需要記錄的關鍵信息尋找需要記錄的關鍵信息 設計識別設計識別0,1上以下語言的上以下語言的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的設計的設計 w 0,1* | w從從1開始開始, 以以0結(jié)束結(jié)束 =0,1, 根據(jù)根據(jù)關鍵信息設計狀態(tài)關鍵信息設計狀態(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的設計的設計 w 0,1* | w含有子串含有子串1010 =0,1, 關鍵信息關鍵信息: 忽略忽略( ), 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的設計的設計 w 0,1* | w倒數(shù)第倒數(shù)第2個符號是個符號是1 =0,1, 關鍵信息關鍵信息: 忽略忽略( ), 1, 1x, 1 1 0 0 10110 1 1 1 0 DFA 1忽略忽略 1 0,1 0,1 1xNFA NFA與與DFA等價等價定理定理: 每個每個NFA都有一臺等價的都有一臺等價的DFA.q1q101q3q2q10q1q31q3q2q1q3q2q1q4q41q1q2q3q40,110,10,1N構造構造DFA 關鍵關鍵信息信息 每個時刻每個時刻 所有所有副本狀態(tài)副本狀態(tài)的集

29、合的集合每個每個NFA都有等價的都有等價的DFAq1q2q3q40,110,10,1編號編號 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)的子集 為新機器的狀態(tài)為新機器的狀態(tài) 每個每個NFA都有等價的都有等價的DFA證明證明: 設設N = (Q1, , 1,s1,F1)

30、是是NFA, /設計設計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到多個到多個 箭頭可達箭頭可達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正則運算的封閉性正則運算的封閉性定理定理: 正則語言對正則語言對并并運算封閉運算封閉.定理定理: 正則語言對正則語言對連接連接運算封閉運算封

31、閉. 定理定理: 正則語言對正則語言對星號星號運算封閉運算封閉. 證明證明: 畫狀態(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 正則表達式正則表達式定義定義: 稱稱R是一個正則表達式是一個正則表達式, 若若R是是 1) a, a ; 2) ; 3) ; 4) (R1 R2), R1和和R2是正則表達式是正則表達式; 5) (R1 R2), R1和和R2是正則表達式是正則表達式; 6) (R1*), R1是正則表達式是正則表達式;每個正則表達式每個正則表達式R表示一個語言表示一個語言(?),記為記為L(R).例例: 0*10*, 01 10, ()*, 1*,

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

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

36、 b b 123a a a b b b sac 添起始狀態(tài)添起始狀態(tài)s(無無進入箭頭進入箭頭), 接受狀態(tài)接受狀態(tài)ac(無射無射出箭頭出箭頭), 改掉其它接受狀態(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 非正則語言非正則語言B= 0n1n | n 0 C= w

37、| w中中0和和1的個數(shù)相等的個數(shù)相等 D= w | w中中01和和10的個數(shù)相等的個數(shù)相等 哪些是哪些是正則語言正則語言?泵引理的等價描述泵引理的等價描述定理定理(泵引理泵引理): 設設A是正則語言是正則語言,則則存在存在p0使得使得 對對任意任意w A, |w| p, 存在存在分割分割w=xyz滿足滿足 1) 對對任意任意 i 0, xyiz A; 2) |y|0; 3) |xy| p. 若若A是正則是正則語言語言, 則則 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非非正則語言正則語言 B = 0n1n | n 0 非正則非正則 p0, 令令w=0p1p, x,y,z(|y|0, |xy| p, w=xyz) 令令i=0, xz = 0p-|y|1p B B非非正則語言正則語言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 則則A非非正則語言正則語言 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非非正則語言正則語言 若若 p0 w A(|w| p) x,y,z(|y|0, |xy| p, w=xyz) i 0, xyiz A. 則則A非非正則語言正則語言 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非非正則語言正則語言泵引理的證明泵引理的證明定理定理(泵引理泵引理): 設設A是正則語言是正則語言,則則存在存在p0使得使得 對對

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

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

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

43、號一些符號, 再再改變他所看到的范圍改變他所看到的范圍. 繼續(xù)繼續(xù), 直到他認為計算結(jié)束直到他認為計算結(jié)束. 腦腦:控制器控制器 紙紙:存儲帶存儲帶 眼睛和筆眼睛和筆:讀寫頭讀寫頭 法則法則:轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)與有限自動機的區(qū)別與有限自動機的區(qū)別有限自動機有限自動機: 輸入帶長度有限輸入帶長度有限 只能只能讀讀和和右移右移, 不能不能寫寫和和左移左移 讀完輸入停機讀完輸入停機圖靈機圖靈機(TM)的形式化定義的形式化定義TM是一個是一個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 .圖靈機的初始化圖靈機的初始化設設M=(Q, , , , q0, qa, qr), w=w1wnn, 輸入帶輸入帶: 將輸入串將輸入串w放在最左端放在最左端n格中格中, 帶子其余部分補充空格帶子其余部分補充空格. 讀寫頭讀寫頭: 指向工作帶最左端指向工作帶最左端.例例:設輸入串為設輸入串為0101, 則其初始形態(tài)為則其初始形態(tài)為圖靈機的運行圖靈機的運行 圖靈機根據(jù)轉(zhuǎn)移函數(shù)運行圖靈機根據(jù)轉(zhuǎn)移函數(shù)運行. 例例:設輸入串

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

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

47、前控制器狀態(tài)狀態(tài)為為q ; 2) 存儲帶存儲帶上字符串為上字符串為uv(其余為空格其余為空格); 3) 讀寫頭讀寫頭指向指向v的第一個符號的第一個符號. 起始格局起始格局, 接受格局接受格局, 拒絕格局拒絕格局.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 _ 拒絕拒絕 圖靈機計算的形式定義圖靈機計算的形式定義稱圖靈機稱圖靈機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的的語言語言: M接受的所有字符串的集合接受的所有字符串的集合, 記為記為L(M).1. 圖靈機基礎圖靈機基礎1.1 圖靈機的定義圖靈機的定義1.2 圖靈機舉例圖靈機舉例1.3 圖靈機的描述圖靈機的描述圖靈機舉例圖靈機舉例 =0,1, A=0w1 : w* 正則語言正則語言 B=0n1n : n 0 上下文無關語言上下文無關語言 =0, C=0k:k=2n,n 0 圖靈圖靈可判定可判定語言語言 M=“對于輸入串對于輸入串w, 1) 若若w= , 則拒絕則拒絕. 2) 若只有若只

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

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

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