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

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

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

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

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

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

7、uAvuwv (Aw是產生式)任意步生成(派生,推導):u*v: uu1u2ukv 或 u=v文法(生成)的語言: L(G)= w* | S*w 上下文無關語言(CFL): CFG生成的語言理論計算機科學基礎31例G1 = ( A,B, 0,1,#, A0A1,AB,B#, A )理論計算機科學基礎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_ , )理論計算機科學基礎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)包含所有匹配的括號串 或空串. 理論計算機科學基礎34例3.3G4=(V,R,), 其中 V=, = a, +, , (, ) , R為 + | | () | a 乘法比加法優先理論計算機科學基礎35例3.3(續) a+aa的語法分析樹 a+aa理論計算機科學基礎36例3.3(續) (a+a)a的語法分析樹+a)aa(設計上下文無關文法理論計算機科學基礎37理論計算機科學基礎38如

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、| a | SA | AS B b A1 SA理論計算機科學基礎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理論計算機科學基礎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 下推自動機的例子理論計算機科學基礎106理論計算機科學基礎107下推自動機(PDA)狀態控

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

26、機(PDA)狀態控制器單向只讀輸入帶0 0 1 1 1單向只讀頭$棧$理論計算機科學基礎114例 0n1n | n0 讀輸入中的符號,每讀一個0,把一個0推入棧一旦看見1之后, 就每讀一個1,把一個0彈出棧l如果當讀完輸入串時, 恰好排空棧中的0, 則接受; 否則拒絕l如果在還有1沒有讀完時, 棧就排空, 則拒絕l如果在1讀完時, 棧中還有0, 則拒絕l如果0出現在1的后面, 則拒絕理論計算機科學基礎115非確定性 0n1n | n0 確定型PDA, 即DPDA anbncm, anbmcn | m,n0 固有歧義非確定型PDA, 即NPDA, 簡稱PDA一般說PDA指的是非確定型PDA下推自

27、動機的定義理論計算機科學基礎116理論計算機科學基礎117PDA的形式定義定義3.8: PDA M=(Q,q0,F), 其中1) Q: 有窮狀態集2) : 輸入字母表, =3) : 棧字母表, =4) : QP(Q), 轉移函數5) q0Q: 初始狀態6) FQ: 接受狀態(終結狀態)集理論計算機科學基礎118PDA計算的形式定義M=(Q,q0,F); 輸入w=w1w2wm, wi計算: 狀態-棧符號串序列 (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*理論計算機科學基礎119PDA計算的形式定義接受計算:3) rmF; (或者同時要求sm=)M接受w: M對輸入w存在接受計算M(識別,接受)的語言: L(M) = x | M接受x 下推自動機的例子理論計算機科學基礎120理論計算機