講義下載-edx

1、第3、第4周內(nèi)容介紹,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,1,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,2,第3、第4周內(nèi)容提要,上下文無(wú)關(guān)語(yǔ)言上下文無(wú)關(guān)文法(CFG)歧義性喬姆斯基范式下推自動(dòng)機(jī)(PDA)PDA與CFG的等價(jià)性泵引理,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,3,與第1、第2周內(nèi)容的對(duì)比,正則語(yǔ)言有窮自動(dòng)機(jī)正則表達(dá)式 (表示正則語(yǔ)言)泵引理 (證明非正則語(yǔ)言)應(yīng)用上下文無(wú)關(guān)語(yǔ)言上下文無(wú)關(guān)文法下推自動(dòng)機(jī)泵引理應(yīng)用 (遞歸結(jié)構(gòu),人類語(yǔ)言,

2、 程序設(shè)計(jì)語(yǔ)言,自動(dòng)處理),兩個(gè)上下文無(wú)關(guān)文法的例子,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,4,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,5,上下文無(wú)關(guān)文法的例子,文法G1: A ? 0A1 A ? B B ? #,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,6,產(chǎn)生式的例子,文法G1: A ? 0A1 A

3、 ? B B ? #產(chǎn)生式(替換規(guī)則): A?0A1, A?B, B?#,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,7,變?cè)睦?文法G1: A ? 0A1 A ? B B ? #變?cè)?非

4、終結(jié)符): A, B,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,8,終結(jié)符的例子,文法G1: A ? 0A1 A ? B B ? #終結(jié)符: 0,1, #,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,9,初始符的例子,文法G1: A ? 0A1 A ? B B ? #初始符: A

5、,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,10,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,11,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1,《理論計(jì)算機(jī)科

6、學(xué)基礎(chǔ)》,12,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,13,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ?

7、 00A11 ? 000A111,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,14,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 ? 000B111,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,15,一步派生的例子,文法G1: A ?

8、 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 ? 000B111 ? 000#111,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,16,語(yǔ)法分析樹(shù)的例子,文法G1: A ? 0A1 A ? B B ? #派生: A語(yǔ)法分析樹(shù),A,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,1

9、7,語(yǔ)法分析樹(shù),文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1語(yǔ)法分析樹(shù),A,A,0,1,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,18,語(yǔ)法分析樹(shù),文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 語(yǔ)法分析樹(shù),A,A,A,0,0,1,1,,,,,,,《理論計(jì)算機(jī)科學(xué)基

10、礎(chǔ)》,19,語(yǔ)法分析樹(shù),文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 語(yǔ)法分析樹(shù),A,A,A,A,0,0,0,1,1,1,,,,,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,20,語(yǔ)法分析樹(shù),文法G1: A ? 0A1 A ? B B ? #派生: A

11、? 0A1 ? 00A11 ? 000A111 ? 000B111語(yǔ)法分析樹(shù),A,A,A,A,B,0,0,0,1,1,1,,,,,,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,21,語(yǔ)法分析樹(shù),文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 ? 000B111 ? 000#11

12、1語(yǔ)法分析樹(shù),A,A,A,A,B,#,0,0,0,1,1,1,,,,,,,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,22,生成的語(yǔ)言,文法G1: A ? 0A1 A ? B B ? #G1生成的語(yǔ)言: L(G1)={ 0n#1n | n?0 },A,A,A,A,B,#,0,0,0,1,1,1,,,,,,,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,23,產(chǎn)生式的縮寫,文法G1:

13、 A ? 0A1 A ? B B ? #縮寫: G1: A ? 0A1 | B B ? #,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,24,G2, ? ? | ? | ? ? ? | ? a_ | the_ ? boy_ | gir

14、l_ | flower_ ? touches_ | likes_ | sees_ ? with_,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,25,G2,a boy seesthe boy sees a flowera girl with a flower likes the boy,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,26,G2,a_boy_sees_the_boy_sees_a_flower_a_girl_with_a_flo

15、wer_likes_the_boy_,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,27,G2, ? ? ? ? a_ ? a_boy_ ? a_boy_ ? a_boy_ ? a_boy_sees_,上下文無(wú)關(guān)文法的定義,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,28,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,29,

16、CFG的形式定義,定義3.1:上下文無(wú)關(guān)文法 G=(V,?,R,S), 1) V: 有窮變?cè)?2) ?: 有窮終結(jié)符集 3) R: 有窮規(guī)則集 ( 規(guī)則形如 A?w, w?(V??)* ) 4) S?V: 初始變?cè)?《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,30,CFG的形式定義,一步生成(派生,推導(dǎo)): uAv?uwv (A?w是產(chǎn)生式)任意步生成(派生,推導(dǎo)):

17、u?*v: u?u1?u2?…?uk?v 或 u=v文法(生成)的語(yǔ)言: L(G)={ w??* | S?*w }上下文無(wú)關(guān)語(yǔ)言(CFL): CFG生成的語(yǔ)言,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,31,例,G1 = ( {A,B}, {0,1,#}, {A?0A1,A?B,B?#}, A ),《理論計(jì)算機(jī)科學(xué)基

18、礎(chǔ)》,32,例,G2=( {,,,,,,,,, }, {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,_}, { ?,?, ?, ?, ?, ?,?,?, ?,?a_, ?the_,?boy_,?girl_,名詞>?flower_,?touches_, ?likes_,?sees_,?with_ }, ),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,33,例3.

19、2,G3=({S},{a,b},R,S), 其中R為 { S ? aSb | SS | ? } S ? SS ? aSbS ? abS ?* abab. S ? aSb ? aaSbb ?* aaabbb. S ? aSb ? aSSb ?* aababb.L(G3)包含所有匹配的括號(hào)串 或空串.,

20、《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,34,例3.3,G4=(V,?,R,), 其中 V={,,}, ?={ a, +, ?, (, ) }, R為 { ?+ | ?? | ?() | a }乘法比加法優(yōu)先,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,35,例3.3(續(xù)),a+a?a的語(yǔ)法分析樹(shù),,,,,,,,,a,+,a,?,a,,,,,,,,,,,,,《理

21、論計(jì)算機(jī)科學(xué)基礎(chǔ)》,36,例3.3(續(xù)),(a+a)?a的語(yǔ)法分析樹(shù),+,a,),?,a,a,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,設(shè)計(jì)上下文無(wú)關(guān)文法,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,37,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,38,如何設(shè)計(jì)CFG,合并正則匹配遞歸,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,39,合并CFG,為 {w|w=0n1n或w=1n0n,n?0} 設(shè)計(jì)CFG.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,40,合并C

22、FG,為 {w|w=0n1n或w=1n0n,n?0} 設(shè)計(jì)CFG.為{w|w=0n1n,n?0}設(shè)計(jì)CFG.為{w|w=1n0n,n?0}設(shè)計(jì)CFG.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,41,合并CFG,為 {w|w=0n1n或w=1n0n,n?0} 設(shè)計(jì)CFG.為{w|w=0n1n,n?0}設(shè)計(jì)CFG.G1=({S},{0,1},{S?0S1,S??},S)為{w|w=1n0n,n?0}設(shè)

23、計(jì)CFG.G2=({S},{0,1},{S?1S0,S??},S),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,42,合并CFG,為 {w|w=0n1n或w=1n0n,n?0} 設(shè)計(jì)CFG.為{w|w=0n1n,n?0}設(shè)計(jì)CFG.G1=({S1},{0,1},{S1?0S11,S1??},S1)為{w|w=1n0n,n?0}設(shè)計(jì)CFG.G2= ({S2},{0,1},{S2?1S20,S2??},S2),《理論計(jì)算機(jī)科學(xué)基

24、礎(chǔ)》,43,合并CFG,為 {w|w=0n1n或w=1n0n,n?0} 設(shè)計(jì)CFG.為{w|w=0n1n,n?0}設(shè)計(jì)CFG.G1=({S1},{0,1},{S1?0S11,S1??},S1)為{w|w=1n0n,n?0}設(shè)計(jì)CFG.G2= ({S2},{0,1},{S2?1S20,S2??},S2)G=({S,S1,S2},{0,1},{ S?S1, S?S2, S1?0S11, S1??, S2?1

25、S20, S2??},S),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,44,合并CFG,一般情況: 增加 S?S1 | S2 |…| Sk S是新的初始變?cè)猄1, S2, …, Sk 是原來(lái)的初始變?cè)?《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,45,合并CFG,一般情況: 增加 S?S1 | S2 |…| Sk S是新的初始變?cè)猄1, S2, …, Sk 是原來(lái)的初始變?cè)ɡ? CFL對(duì)并運(yùn)算封閉. #,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,46,正則

26、語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,47,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,48,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG設(shè)DFA M=(Q,?,?,q0,F)則CFG G=(V,?,R,R0),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,49,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG設(shè)DFA M=(Q,?,?,q0,F)Q={q0,q1,

27、…,qk},則CFG G=(V,?,R,R0)V={R0,R1,…,Rk},,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,50,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG設(shè)DFA M=(Q,?,?,q0,F)?(qi,a)=qj,則CFG G=(V,?,R,R0)Ri?aRj,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,51,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG設(shè)DFA M=(Q,?,?,q0,F)qi?F則CFG

28、 G=(V,?,R,R0)Ri??,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,52,正則語(yǔ)言,為正則語(yǔ)言設(shè)計(jì)CFG.把DFA轉(zhuǎn)換成等價(jià)的CFG設(shè)DFA M=(Q,?,?,q0,F)Q={q0,q1,…,qk}, ?(qi,a)=qj, qi?F則CFG G=(V,?,R,R0)V={R0,R1,…,Rk}, Ri?aRj, Ri??定理: 正則語(yǔ)言都是 上下文無(wú)關(guān)語(yǔ)言.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,53,某些匹配,0n1

29、n,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,54,某些匹配,0n1nR?0R1, R??,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,55,某些匹配,0n1nR?0R1, R??0000011111,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,56,某些匹配,0n1nR?0R1, R??0000011111,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,57,某些匹配,0n1nR?0R1, R??0000011111wwR倒置: w=11010, wR=01011,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》

30、,58,某些匹配,wwR倒置: w=11010, wR=01011 可用上下文無(wú)關(guān)文法生成,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,59,某些匹配,wwR倒置: w=11010, wR=01011 可用上下文無(wú)關(guān)文法生成ww,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,60,某些匹配,wwR倒置: w=11010, wR=01011上下文無(wú)關(guān)ww非正則, 非上下文無(wú)關(guān),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,61,某些匹配,wwR倒置: w=11010, wR=010

31、11上下文無(wú)關(guān)ww非正則, 非上下文無(wú)關(guān)非ww,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,62,某些匹配,wwR倒置: w=11010, wR=01011上下文無(wú)關(guān)ww非正則, 非上下文無(wú)關(guān)非ww上下文無(wú)關(guān),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,63,遞歸結(jié)構(gòu),(a+a)?a((a+a)+a)?a,+,a,),?,a,a,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,文法的歧義性,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,64,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)

32、》,65,歧義性,G5: ? + | ? | () | a,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,66,不同的分析樹(shù),,,,a,+,a,?,a,,,,,,,,,,,,,,,a,?,a,,,,,,a,+,,,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,67,不同的結(jié)構(gòu)與不同的意義,G2:the_girl_touches_the_boy_with_flower,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,6

33、8,最左派生,最左派生: 每一步都替換最左邊的變?cè)?《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,69,最左派生的例子, ? + ? a+ ? a+? ? a+a? ? a+a?a,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,70,兩個(gè)不同的最左派生, ? + ? a+ ? a+? ? a+a? ? a+a?a ? ? ? + ? ? a+? ? a+a? ? a+a?a,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,71,歧義

34、性地產(chǎn)生,最左派生: 每一步都替換最左邊的變?cè)缌x地產(chǎn)生: 有兩個(gè)不同的最左派生,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,72,歧義文法,最左派生: 每一步都替換最左邊的變?cè)缌x地產(chǎn)生: 有兩個(gè)不同的最左派生歧義文法: 文法歧義地產(chǎn)生某個(gè)串,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,73,固有歧義性,最左派生: 每一步都替換最左邊的變?cè)缌x地產(chǎn)生: 有兩個(gè)不同的最左派生歧義文法:

35、 文法歧義地產(chǎn)生某個(gè)串固有歧義語(yǔ)言: 只能用歧義文法產(chǎn)生,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,74,固有歧義語(yǔ)言的例子,固有歧義語(yǔ)言: 只能用歧義文法產(chǎn)生例: { 0i1j2k | i=j 或 j=k }{ 0n1n2m | n,m?0 } ? { 0m1n2n | n,m?0 }0n1n2n只能歧義地產(chǎn)生,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,75,歧義性與非確定性,固有歧義性 (Inherent Ambigui

36、ty)非確定性 (Nondeterminism),喬姆斯基范式的定義,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,76,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,77,喬姆斯基范式(CNF),CNF: 只允許如下形式的規(guī)則: S??A?BCA?a其中A,B,C是任意變?cè)狟,C不是初始變?cè)?(初始變?cè)荒茉谟曳匠霈F(xiàn)) a是任意終結(jié)符,求喬姆斯基范式的算法,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,78,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,79,喬姆斯基范式(CNF),等價(jià):

37、 兩個(gè)文法生成同樣語(yǔ)言定理3.6: 任何CFG都有 等價(jià)的CNF.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,80,定理3.6,定理3.6: 任何CFG都有 等價(jià)的CNF.證明思路: 下列算法：1) 添加新的初始變?cè)?) 處理A?? (?規(guī)則)3) 處理A?B (單一規(guī)則)4) 處理A?u1u2…uk (k?3)5) 處理A?aiaj, A?a

38、iB, A?Bai,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,81,添加新初始變?cè)?1) 添加新初始變?cè)猄0和規(guī)則 S0?S, 其中S是舊初始變?cè)?,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,82,處理?規(guī)則,2) 考慮所有?規(guī)則. 若A不是初始變?cè)?則刪除A??, 以各種可能的方式刪除其他規(guī)則右邊的A,添加新的規(guī)則,例如 由B?uAv添加B?uv 由B?uAvAw添加B?uvAw | uAvw |

39、 uvw 由B?A添加B?? (除非已刪除過(guò)B??)直到刪除所有?規(guī)則(S0??除外)為止.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,83,處理單一規(guī)則,3) 處理所有單一規(guī)則. 刪除A?B, 若有規(guī)則B?u, 則添加規(guī)則A?u, 除非A?u是已刪除過(guò)的單一規(guī)則. 重復(fù)上述步驟, 直到刪除所有單一規(guī)則為止.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,84,處理A?u1u2…uk規(guī)則,4

40、) 把每一條規(guī)則A?u1u2…uk換成 A?u1A1 A1?u2A2 A2?u3A3 … Ak-2?uk-1uk (k?3),《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,85,處理終結(jié)符,5) 對(duì)每個(gè)終結(jié)符ai， 引入變?cè)猆i和規(guī)則Ui?ai. 把A?aiaj換成A?UiUj 把A?aiB換成A?UiB 把A?Bai換

41、成A?Bui可以證明，這樣求出的是等價(jià)的喬姆斯基范式 ， 定理3.6證明完畢。,求喬姆斯基范式的例子,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,86,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,87,例3.7,G6: S ? ASA | aB, A ? B | S B ? b | ? 求等價(jià)CNF.,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,88,例3.7(1),G6: S ? ASA | aB, A ? B |

42、 S B ? b | ?(1) S0 ? S S ? ASA | aB A ? B | S B ? b | ?,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,89,例3.7(2a),(2a) S0 ? S S ? ASA | aB A ? B | S B ? b | ?,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,90,例3.7(2a),(2a) S0

43、 ? S S ? ASA | aB | a A ? B | S | ? B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,91,例3.7(2b),(2b) S0 ? S S ? ASA | aB | a A ? B | S | ? B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,92,例3.7(2b),(2b) S0 ? S S ?

44、ASA | aB | a | SA | AS | S A ? B | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,93,例3.7(3a),(3a) S0 ? S S ? ASA | aB | a | SA | AS | S A ? B | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》

45、,94,例3.7(3a),(3a) S0 ? S S ? ASA | aB | a | SA | AS A ? B | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,95,例3.7(3b),(3b) S0 ? S S ? ASA | aB | a | SA | AS A ? B

46、 | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,96,例3.7(3b),(3b) S0 ? ASA | aB | a | SA | AS S ? ASA | aB | a | SA | AS A ? B | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,97,例3.7(3c),(3c) S0 ? ASA

47、 | aB | a | SA | AS S ? ASA | aB | a | SA | AS A ? B | S B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,98,例3.7(3c),(3c) S0 ? ASA | aB | a | SA | AS S ? ASA | aB

48、| a | SA | AS A ? S | b B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,99,例3.7(3d),(3d) S0 ? ASA | aB | a | SA | AS S ? ASA | aB | a | SA | AS A ? S | b B ? b

49、,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,100,例3.7(3d),(3d) S0 ? ASA | aB | a | SA | AS S ? ASA | aB | a | SA | AS A ? b | ASA | aB | a | SA | AS B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,101,例

50、3.7(4),(4) S0 ? ASA | aB | a | SA | AS S ? ASA | aB | a | SA | AS A ? b | ASA | aB | a | SA | AS B ? b,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,102,例3.7(4),(4) S0 ? AA1

51、 | aB | a | SA | AS S ? AA2 | aB | a | SA | AS A ? b | AA3 | aB | a | SA | AS B ? b A1 ? SA A2 ? SA A3 ? SA,《理論計(jì)算機(jī)科學(xué)基

52、礎(chǔ)》,103,例3.7(4),(4) S0 ? AA1 | aB | a | SA | AS S ? AA1 | aB | a | SA | AS A ? b | AA1 | aB | a | SA | AS B ? b A1 ? SA,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,10

53、4,例3.7(5),(5) S0 ? AA1 | aB | a | SA | AS S ? AA1 | aB | a | SA | AS A ? b | AA1 | aB | a | SA | AS B ? b A1 ? SA,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,105,例3.7(5)-完成,(5)

54、S0 ? AA1 | UB | a | SA | AS S ? AA1 | UB | a | SA | AS A ? b | AA1 | UB | a | SA | AS B ? b A1 ? SA U ? a,下推自動(dòng)機(jī)的例子,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,106,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,

55、107,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,,,,棧,$,,,$,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,108,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,$,,,,棧,$,,,$,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,109,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀

56、頭,,,,,$,,,,棧,$,,,$,,,,,,0,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,110,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,$,,,,棧,$,,,$,,,,,,0,0,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,111,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,$,,,,棧,$,,,$,,,,,,0,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,112,

57、下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,$,,,,棧,$,,,$,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,113,下推自動(dòng)機(jī)(PDA),,狀態(tài)控制器,,,,,,,單向只讀輸入帶,0,0,1,1,1,單向只讀頭,,,,,$,,,,棧,$,,,$,,,,,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,114,例,{ 0n1n | n?0 }讀輸入中的符號(hào),每讀一個(gè)0,把一個(gè)0推入棧一旦看見(jiàn)1之后,

58、 就每讀一個(gè)1,把一個(gè)0彈出棧如果當(dāng)讀完輸入串時(shí), 恰好排空棧中的0, 則接受; 否則拒絕如果在還有1沒(méi)有讀完時(shí), 棧就排空, 則拒絕如果在1讀完時(shí), 棧中還有0, 則拒絕如果0出現(xiàn)在1的后面, 則拒絕,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,115,非確定性,{ 0n1n | n?0 }確定型PDA, 即DPDA{ anbncm, anbmcn | m,n?0 }固有歧義非確定型PDA, 即NPDA, 簡(jiǎn)稱

59、PDA一般說(shuō)PDA指的是非確定型PDA,下推自動(dòng)機(jī)的定義,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,116,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,117,PDA的形式定義,定義3.8: PDA M=(Q,?,?,?,q0,F), 其中1) Q: 有窮狀態(tài)集2) ?: 輸入字母表, ??=??{?}3) ?: 棧字母表, ??=??{?}4) ?: Q???????P(Q???), 轉(zhuǎn)移函數(shù)5) q0?Q: 初始狀態(tài)6) F?Q:

60、接受狀態(tài)(終結(jié)狀態(tài))集,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,118,PDA計(jì)算的形式定義,M=(Q,?,?,?,q0,F); 輸入w=w1w2…wm, wi???計(jì)算: 狀態(tài)-棧符號(hào)串序列 (r0,s0), (r1,s1),…, (rm ,sm), 其中 ri?Q, si??*, 滿足 1) (r0,s0)=(q0,?); 2) (ri+1,b)??(ri,wi+1,a); 其中 si

61、=at; si+1=bt, a,b???, t??*,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,119,PDA計(jì)算的形式定義,接受計(jì)算:3) rm?F; (或者同時(shí)要求sm=?)M接受w: M對(duì)輸入w存在接受計(jì)算M(識(shí)別,接受)的語(yǔ)言: L(M) = { x | M接受x },下推自動(dòng)機(jī)的例子,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,120,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,121,例3.9,L(M1)={ 0n1n | n?

62、0 },《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,122,例3.9,L(M1)={ 0n1n | n?0 }M1=({q1,q2,q3,q4},{0,1},{0,$},?,q1,{q1,q4}),?表,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,123,例3.9 (用$判斷是否空棧),L(M1)={ 0n1n | n?0 },,,q1,,q2,,,q4,,q3,,,,,,?, ??$,0, ??0,1, 0? ?,1, 0? ?,?, $? ?,,M1,《理論計(jì)算機(jī)科學(xué)基

63、礎(chǔ)》,124,例3.10,L(M2)={ anbncm, anbmcn | m,n?0 },,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,125,例3.10,L(M2)={ anbncm, anbmcn | m,n?0 },先讀a,并且把a(bǔ)推入堆棧利用非確定性, 猜想a是與b匹配還是與c匹配與b匹配每讀到一個(gè)輸入符號(hào)b,就從堆棧中 彈出一個(gè)a,若從輸入中讀b結(jié)束時(shí) 堆棧排空,則讀若干個(gè)c后接受; 否則拒絕與c匹配讀若干個(gè)b后,每

64、讀到一個(gè)輸入符號(hào)c, 就從堆棧中彈出一個(gè)a, 若輸入結(jié)束時(shí) 堆棧排空,則接受;否則拒絕,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,126,例3.10,L(M2)={ anbncm, anbmcn | m,n?0 },,,q1,,,q2,,q5,,,q7,,q3,,,q4,,q6,,,,,,,,,,,,?, ??$,?, ???,?, ???,?, ???,?, $??,?, $??,b, a??,c, ???,b, ???,a, ??a,c,

65、 a??,M2,,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,127,例3.11,L(M3)={ wwR | w?{0,1}* },《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,128,例3.11,L(M3)={ wwR | w?{0,1}* }開(kāi)始時(shí),把讀到的符號(hào)推入堆棧中在每一步,非確定性地猜測(cè)已到達(dá) 字符串的中點(diǎn),然后變成把讀到的每一個(gè)符號(hào)彈出堆棧, 檢查在輸入中和在堆棧頂 讀到的符號(hào)是否一樣如果它們總是一樣的, 并且輸入結(jié)束時(shí)堆棧同時(shí)排空

66、, 則接受;否則拒絕,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,129,例3.11,L(M3)={ wwR | w?{0,1}* },,,q1,,q2,,,q4,,q3,,,,,,?, ??$,0, ??0,?, ???,0, 0? ?,?, $? ?,,M3,1, ??1,1, 1? ?,《理論計(jì)算機(jī)科學(xué)基礎(chǔ)》,130,總結(jié),概念上下文無(wú)關(guān)文法(CFG)上下文無(wú)關(guān)語(yǔ)言(CFL)派生,最左派生,固有歧義性喬姆斯基范式(CNF)下推自動(dòng)機(jī)(