第3、第4周內(nèi)容介紹

1、第3、第4周內(nèi)容介紹理論計算機科學(xué)基礎(chǔ)1理論計算機科學(xué)基礎(chǔ)2第3、第4周內(nèi)容提要上下文無關(guān)語言上下文無關(guān)文法(CFG)歧義性喬姆斯基范式下推自動機(PDA)PDA與CFG的等價性泵引理理論計算機科學(xué)基礎(chǔ)3與第1、第2周內(nèi)容的對比正則語言有窮自動機正則表達(dá)式 (表示正則語言)泵引理 (證明非正則語言)應(yīng)用上下文無關(guān)語言上下文無關(guān)文法下推自動機泵引理應(yīng)用 (遞歸結(jié)構(gòu),人類語言, 程序設(shè)計語言,自動處理)兩個上下文無關(guān)文法的例子理論計算機科學(xué)基礎(chǔ)4理論計算機科學(xué)基礎(chǔ)5上下文無關(guān)文法的例子文法G1: A 0A1 A B B # 理論計算機科學(xué)基礎(chǔ)6產(chǎn)生式的例子文法G1: A 0A1 A B B #產(chǎn)生

2、式(替換規(guī)則): A0A1, AB, B#理論計算機科學(xué)基礎(chǔ)7變元的例子文法G1: A 0A1 A B B #變元(非終結(jié)符): A, B理論計算機科學(xué)基礎(chǔ)8終結(jié)符的例子文法G1: A 0A1 A B B #終結(jié)符: 0,1, # 理論計算機科學(xué)基礎(chǔ)9初始符的例子文法G1: A 0A1 A B B #初始符: A 理論計算機科學(xué)基礎(chǔ)10一步派生的例子文法G1: A 0A1 A B B #派生: A理論計算機科學(xué)基礎(chǔ)11一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1理論計算機科學(xué)基礎(chǔ)12一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11理論

3、計算機科學(xué)基礎(chǔ)13一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111理論計算機科學(xué)基礎(chǔ)14一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111理論計算機科學(xué)基礎(chǔ)15一步派生的例子文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111 000#111理論計算機科學(xué)基礎(chǔ)16語法分析樹的例子文法G1: A 0A1 A B B #派生: A語法分析樹A理論計算機科學(xué)基礎(chǔ)17語法分析樹文法G1: A 0A1 A B B #派生: A 0A1語法分析樹

4、AA01理論計算機科學(xué)基礎(chǔ)18語法分析樹文法G1: A 0A1 A B B #派生: A 0A1 00A11 語法分析樹AAA0011理論計算機科學(xué)基礎(chǔ)19語法分析樹文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 語法分析樹AAAA000111理論計算機科學(xué)基礎(chǔ)20語法分析樹文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111語法分析樹AAAAB000111理論計算機科學(xué)基礎(chǔ)21語法分析樹文法G1: A 0A1 A B B #派生: A 0A1 00A11 000A111 000B111 000#111語法分

5、析樹AAAAB#000111理論計算機科學(xué)基礎(chǔ)22生成的語言文法G1: A 0A1 A B B #G1生成的語言: L(G1)= 0n#1n | n0 AAAAB#000111理論計算機科學(xué)基礎(chǔ)23產(chǎn)生式的縮寫文法G1: A 0A1 A B B #縮寫: G1: A 0A1 | B B #理論計算機科學(xué)基礎(chǔ)24G2 | | | a_ | the_ boy_ | girl_ | flower_ touches_ | likes_ | sees_ with_理論計算機科學(xué)基礎(chǔ)25G2a boy seesthe boy sees a flowera girl with a flower likes

6、the boy理論計算機科學(xué)基礎(chǔ)26G2a_boy_sees_the_boy_sees_a_flower_a_girl_with_a_flower_likes_the_boy_理論計算機科學(xué)基礎(chǔ)27G2 a_ a_boy_ a_boy_ a_boy_ a_boy_sees_上下文無關(guān)文法的定義理論計算機科學(xué)基礎(chǔ)28理論計算機科學(xué)基礎(chǔ)29CFG的形式定義定義3.1:上下文無關(guān)文法 G=(V,R,S), 1) V: 有窮變元集 2) : 有窮終結(jié)符集 3) R: 有窮規(guī)則集 ( 規(guī)則形如 Aw, w(V)* ) 4) SV: 初始變元理論計算機科學(xué)基礎(chǔ)30CFG的形式定義一步生成(派生,推導(dǎo)):

7、uAvuwv (Aw是產(chǎn)生式)任意步生成(派生,推導(dǎo)):u*v: uu1u2ukv 或 u=v文法(生成)的語言: L(G)= w* | S*w 上下文無關(guān)語言(CFL): CFG生成的語言理論計算機科學(xué)基礎(chǔ)31例G1 = ( A,B, 0,1,#, A0A1,AB,B#, A )理論計算機科學(xué)基礎(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_ , )理論計算機科學(xué)基礎(chǔ)3

8、3例3.2G3=(S,a,b,R,S), 其中R為 S aSb | SS | S SS aSbS abS * abab. S aSb aaSbb * aaabbb. S aSb aSSb * aababb.L(G3)包含所有匹配的括號串 或空串. 理論計算機科學(xué)基礎(chǔ)34例3.3G4=(V,R,), 其中 V=, = a, +, , (, ) , R為 + | | () | a 乘法比加法優(yōu)先理論計算機科學(xué)基礎(chǔ)35例3.3(續(xù)) a+aa的語法分析樹a+aa理論計算機科學(xué)基礎(chǔ)36例3.3(續(xù)) (a+a)a的語法分析樹+a)aa(設(shè)計上下文無關(guān)文法理論計算機科學(xué)基礎(chǔ)37理論計算機科學(xué)基礎(chǔ)38如何

9、設(shè)計CFG合并正則匹配遞歸理論計算機科學(xué)基礎(chǔ)39合并CFG為 w|w=0n1n或w=1n0n,n0 設(shè)計CFG.理論計算機科學(xué)基礎(chǔ)40合并CFG為 w|w=0n1n或w=1n0n,n0 設(shè)計CFG.為w|w=0n1n,n0設(shè)計CFG.為w|w=1n0n,n0設(shè)計CFG.理論計算機科學(xué)基礎(chǔ)41合并CFG為 w|w=0n1n或w=1n0n,n0 設(shè)計CFG.為w|w=0n1n,n0設(shè)計CFG.G1=(S,0,1,S0S1,S,S)為w|w=1n0n,n0設(shè)計CFG.G2=(S,0,1,S1S0,S,S)理論計算機科學(xué)基礎(chǔ)42合并CFG為 w|w=0n1n或w=1n0n,n0 設(shè)計CFG.為w|w=

10、0n1n,n0設(shè)計CFG.G1=(S1,0,1,S10S11,S1,S1)為w|w=1n0n,n0設(shè)計CFG.G2= (S2,0,1,S21S20,S2,S2)理論計算機科學(xué)基礎(chǔ)43合并CFG為 w|w=0n1n或w=1n0n,n0 設(shè)計CFG.為w|w=0n1n,n0設(shè)計CFG.G1=(S1,0,1,S10S11,S1,S1)為w|w=1n0n,n0設(shè)計CFG.G2= (S2,0,1,S21S20,S2,S2)G=(S,S1,S2,0,1, SS1, SS2, S10S11, S1, S21S20, S2,S)理論計算機科學(xué)基礎(chǔ)44合并CFG一般情況: 增加 SS1 | S2 | Sk S是

11、新的初始變元S1, S2, , Sk 是原來的初始變元理論計算機科學(xué)基礎(chǔ)45合并CFG一般情況: 增加 SS1 | S2 | Sk S是新的初始變元S1, S2, , Sk 是原來的初始變元定理: CFL對并運算封閉. # 理論計算機科學(xué)基礎(chǔ)46正則語言為正則語言設(shè)計CFG.理論計算機科學(xué)基礎(chǔ)47正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG理論計算機科學(xué)基礎(chǔ)48正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG設(shè)DFA M=(Q,q0,F)則CFG G=(V,R,R0)理論計算機科學(xué)基礎(chǔ)49正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG設(shè)DFA M=(Q,q0,F)

12、Q=q0,q1,qk,則CFG G=(V,R,R0)V=R0,R1,Rk,理論計算機科學(xué)基礎(chǔ)50正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG設(shè)DFA M=(Q,q0,F)(qi,a)=qj,則CFG G=(V,R,R0)RiaRj,理論計算機科學(xué)基礎(chǔ)51正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG設(shè)DFA M=(Q,q0,F)qiF則CFG G=(V,R,R0)Ri理論計算機科學(xué)基礎(chǔ)52正則語言為正則語言設(shè)計CFG.把DFA轉(zhuǎn)換成等價的CFG設(shè)DFA M=(Q,q0,F)Q=q0,q1,qk, (qi,a)=qj, qiF則CFG G=(V,R,R0)V=R0,R1,R

13、k, RiaRj, Ri定理: 正則語言都是 上下文無關(guān)語言.理論計算機科學(xué)基礎(chǔ)53某些匹配0n1n理論計算機科學(xué)基礎(chǔ)54某些匹配0n1nR0R1, R理論計算機科學(xué)基礎(chǔ)55某些匹配0n1nR0R1, R0000011111理論計算機科學(xué)基礎(chǔ)56某些匹配0n1nR0R1, R0000011111理論計算機科學(xué)基礎(chǔ)57某些匹配0n1nR0R1, R0000011111wwR倒置: w=11010, wR=01011理論計算機科學(xué)基礎(chǔ)58某些匹配wwR倒置: w=11010, wR=01011 可用上下文無關(guān)文法生成理論計算機科學(xué)基礎(chǔ)59某些匹配wwR倒置: w=11010, wR=01011 可

14、用上下文無關(guān)文法生成ww理論計算機科學(xué)基礎(chǔ)60某些匹配wwR倒置: w=11010, wR=01011上下文無關(guān)ww非正則, 非上下文無關(guān)理論計算機科學(xué)基礎(chǔ)61某些匹配wwR倒置: w=11010, wR=01011上下文無關(guān)ww非正則, 非上下文無關(guān)非ww理論計算機科學(xué)基礎(chǔ)62某些匹配wwR倒置: w=11010, wR=01011上下文無關(guān)ww非正則, 非上下文無關(guān)非ww上下文無關(guān)理論計算機科學(xué)基礎(chǔ)63遞歸結(jié)構(gòu)(a+a)a(a+a)+a)a+a)aa(文法的歧義性理論計算機科學(xué)基礎(chǔ)64理論計算機科學(xué)基礎(chǔ)65歧義性G5: + | | () | a理論計算機科學(xué)基礎(chǔ)66不同的分析樹a+aaa

15、aa+理論計算機科學(xué)基礎(chǔ)67不同的結(jié)構(gòu)與不同的意義G2:the_girl_touches_the_boy_with_flower理論計算機科學(xué)基礎(chǔ)68最左派生最左派生: 每一步都替換最左邊的變元理論計算機科學(xué)基礎(chǔ)69最左派生的例子 + a+ a+ a+a a+aa理論計算機科學(xué)基礎(chǔ)70兩個不同的最左派生 + a+ a+ a+a a+aa + a+ a+a a+aa理論計算機科學(xué)基礎(chǔ)71歧義性地產(chǎn)生最左派生: 每一步都替換最左邊的變元歧義地產(chǎn)生: 有兩個不同的最左派生理論計算機科學(xué)基礎(chǔ)72歧義文法最左派生: 每一步都替換最左邊的變元歧義地產(chǎn)生: 有兩個不同的最左派生歧義文法: 文法歧義地產(chǎn)生某個

16、串理論計算機科學(xué)基礎(chǔ)73固有歧義性最左派生: 每一步都替換最左邊的變元歧義地產(chǎn)生: 有兩個不同的最左派生歧義文法: 文法歧義地產(chǎn)生某個串固有歧義語言: 只能用歧義文法產(chǎn)生理論計算機科學(xué)基礎(chǔ)74固有歧義語言的例子固有歧義語言: 只能用歧義文法產(chǎn)生例: 0i1j2k | i=j 或 j=k 0n1n2m | n,m0 0m1n2n | n,m0 0n1n2n只能歧義地產(chǎn)生理論計算機科學(xué)基礎(chǔ)75歧義性與非確定性固有歧義性 (Inherent Ambiguity)非確定性 (Nondeterminism)喬姆斯基范式的定義理論計算機科學(xué)基礎(chǔ)76理論計算機科學(xué)基礎(chǔ)77喬姆斯基范式(CNF)CNF: 只允

17、許如下形式的規(guī)則: SABCAa其中A,B,C是任意變元B,C不是初始變元 (初始變元不能在右方出現(xiàn)) a是任意終結(jié)符求喬姆斯基范式的算法理論計算機科學(xué)基礎(chǔ)78理論計算機科學(xué)基礎(chǔ)79喬姆斯基范式(CNF)等價: 兩個文法生成同樣語言定理3.6: 任何CFG都有 等價的CNF.理論計算機科學(xué)基礎(chǔ)80定理3.6定理3.6: 任何CFG都有 等價的CNF.證明思路: 下列算法：1) 添加新的初始變元2) 處理A (規(guī)則)3) 處理AB (單一規(guī)則)4) 處理Au1u2uk (k3)5) 處理Aaiaj, AaiB, ABai理論計算機科學(xué)基礎(chǔ)81添加新初始變元1) 添加新初始變元S0和規(guī)則 S0S,

18、 其中S是舊初始變元.理論計算機科學(xué)基礎(chǔ)82處理規(guī)則2) 考慮所有規(guī)則. 若A不是初始變元,則刪除A, 以各種可能的方式刪除其他規(guī)則右邊的A,添加新的規(guī)則,例如 由BuAv添加Buv 由BuAvAw添加BuvAw | uAvw | uvw 由BA添加B (除非已刪除過B)直到刪除所有規(guī)則(S0除外)為止.理論計算機科學(xué)基礎(chǔ)83處理單一規(guī)則3) 處理所有單一規(guī)則. 刪除AB, 若有規(guī)則Bu, 則添加規(guī)則Au, 除非Au是已刪除過的單一規(guī)則. 重復(fù)上述步驟, 直到刪除所有單一規(guī)則為止. 理論計算機科學(xué)基礎(chǔ)84處理Au1u2uk規(guī)則4) 把每一條規(guī)則Au1u2uk換成 Au1A1 A1u2A2 A2

19、u3A3 Ak-2uk-1uk (k3)理論計算機科學(xué)基礎(chǔ)85處理終結(jié)符5) 對每個終結(jié)符ai， 引入變元Ui和規(guī)則Uiai. 把Aaiaj換成AUiUj 把AaiB換成AUiB 把ABai換成ABui可以證明，這樣求出的是等價的喬姆斯基范式 ， 定理3.6證明完畢。求喬姆斯基范式的例子理論計算機科學(xué)基礎(chǔ)86理論計算機科學(xué)基礎(chǔ)87例3.7 G6: S ASA | aB, A B | S B b | 求等價CNF.理論計算機科學(xué)基礎(chǔ)88例3.7(1)G6: S ASA | aB, A B | S B b | (1) S0 S S ASA | aB A B | S B b | 理論計算機科學(xué)基礎(chǔ)8

20、9例3.7(2a)(2a) S0 S S ASA | aB A B | S B b | 理論計算機科學(xué)基礎(chǔ)90例3.7(2a)(2a) S0 S S ASA | aB | a A B | S | B b理論計算機科學(xué)基礎(chǔ)91例3.7(2b)(2b) S0 S S ASA | aB | a A B | S | B b理論計算機科學(xué)基礎(chǔ)92例3.7(2b)(2b) S0 S S ASA | aB | a | SA | AS | S A B | S B b理論計算機科學(xué)基礎(chǔ)93例3.7(3a)(3a) S0 S S ASA | aB | a | SA | AS | S A B | S B b理論計算

21、機科學(xué)基礎(chǔ)94例3.7(3a)(3a) S0 S S ASA | aB | a | SA | AS A B | S B b理論計算機科學(xué)基礎(chǔ)95例3.7(3b)(3b) S0 S S ASA | aB | a | SA | AS A B | S B b理論計算機科學(xué)基礎(chǔ)96例3.7(3b)(3b) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B b理論計算機科學(xué)基礎(chǔ)97例3.7(3c)(3c) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A B | S B b理論

22、計算機科學(xué)基礎(chǔ)98例3.7(3c)(3c) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A S | b B b理論計算機科學(xué)基礎(chǔ)99例3.7(3d)(3d) S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A S | b B b理論計算機科學(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理論計算機科學(xué)基礎(chǔ)101例3.7(4)(4)

23、 S0 ASA | aB | a | SA | AS S ASA | aB | a | SA | AS A b | ASA | aB | a | SA | AS B b理論計算機科學(xué)基礎(chǔ)102例3.7(4)(4) S0 AA1 | 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理論計算機科學(xué)基礎(chǔ)103例3.7(4)(4) S0 AA1 | aB | a | SA | AS S AA1 | aB | a | SA | AS A b | AA1 | aB | a

24、 | SA | AS B b A1 SA理論計算機科學(xué)基礎(chǔ)104例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理論計算機科學(xué)基礎(chǔ)105例3.7(5)-完成(5) 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 下推自動機的例子理論計算機科學(xué)基礎(chǔ)106理論計算機科學(xué)基礎(chǔ)107下推自動機(PDA)狀態(tài)控制器單

25、向只讀輸入帶00111單向只讀頭棧$理論計算機科學(xué)基礎(chǔ)108下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀頭$棧$理論計算機科學(xué)基礎(chǔ)109下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀頭$棧$0理論計算機科學(xué)基礎(chǔ)110下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀頭$棧$00理論計算機科學(xué)基礎(chǔ)111下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀頭$棧$0理論計算機科學(xué)基礎(chǔ)112下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀頭$棧$理論計算機科學(xué)基礎(chǔ)113下推自動機(PDA)狀態(tài)控制器單向只讀輸入帶00111單向只讀

26、頭$棧$理論計算機科學(xué)基礎(chǔ)114例 0n1n | n0 讀輸入中的符號,每讀一個0,把一個0推入棧一旦看見1之后, 就每讀一個1,把一個0彈出棧如果當(dāng)讀完輸入串時, 恰好排空棧中的0, 則接受; 否則拒絕如果在還有1沒有讀完時, 棧就排空, 則拒絕如果在1讀完時, 棧中還有0, 則拒絕如果0出現(xiàn)在1的后面, 則拒絕理論計算機科學(xué)基礎(chǔ)115非確定性 0n1n | n0 確定型PDA, 即DPDA anbncm, anbmcn | m,n0 固有歧義非確定型PDA, 即NPDA, 簡稱PDA一般說PDA指的是非確定型PDA下推自動機的定義理論計算機科學(xué)基礎(chǔ)116理論計算機科學(xué)基礎(chǔ)117PDA的形式

27、定義定義3.8: PDA M=(Q,q0,F), 其中1) Q: 有窮狀態(tài)集2) : 輸入字母表, =3) : 棧字母表, =4) : QP(Q), 轉(zhuǎn)移函數(shù)5) q0Q: 初始狀態(tài)6) FQ: 接受狀態(tài)(終結(jié)狀態(tài))集理論計算機科學(xué)基礎(chǔ)118PDA計算的形式定義M=(Q,q0,F); 輸入w=w1w2wm, wi計算: 狀態(tài)-棧符號串序列 (r0,s0), (r1,s1), (rm ,sm), 其中 riQ, si*, 滿足 1) (r0,s0)=(q0,); 2) (ri+1,b)(ri,wi+1,a); 其中 si=at; si+1=bt, a,b, t*理論計算機科學(xué)基礎(chǔ)119PDA計算的形式定義接受計算:3) rmF; (或者同時要求sm=)M接受w: M對輸入w存在接受計算M(識別,接受)的語言: L(M) = x | M接受x 下推自動機的例子理論計算機科學(xué)基礎(chǔ)120理論