講義下載-edx

1、第3、第4周內容介紹,,《理論計算機科學基礎》,1,《理論計算機科學基礎》,2,第3、第4周內容提要,上下文無關語言上下文無關文法(CFG)歧義性喬姆斯基范式下推自動機(PDA)PDA與CFG的等價性泵引理,《理論計算機科學基礎》,3,與第1、第2周內容的對比,正則語言有窮自動機正則表達式 (表示正則語言)泵引理 (證明非正則語言)應用上下文無關語言上下文無關文法下推自動機泵引理應用 (遞歸結構,人類語言,

2、 程序設計語言,自動處理),兩個上下文無關文法的例子,,《理論計算機科學基礎》,4,《理論計算機科學基礎》,5,上下文無關文法的例子,文法G1: A ? 0A1 A ? B B ? #,《理論計算機科學基礎》,6,產生式的例子,文法G1: A ? 0A1 A

3、 ? B B ? #產生式(替換規(guī)則): A?0A1, A?B, B?#,《理論計算機科學基礎》,7,變元的例子,文法G1: A ? 0A1 A ? B B ? #變元(非

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

5、,《理論計算機科學基礎》,10,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A,《理論計算機科學基礎》,11,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1,《理論計算機科

6、學基礎》,12,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11,《理論計算機科學基礎》,13,一步派生的例子,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ?

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

8、 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 ? 000B111 ? 000#111,《理論計算機科學基礎》,16,語法分析樹的例子,文法G1: A ? 0A1 A ? B B ? #派生: A語法分析樹,A,《理論計算機科學基礎》,1

9、7,語法分析樹,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1語法分析樹,A,A,0,1,,,,《理論計算機科學基礎》,18,語法分析樹,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 語法分析樹,A,A,A,0,0,1,1,,,,,,,《理論計算機科學基

10、礎》,19,語法分析樹,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 語法分析樹,A,A,A,A,0,0,0,1,1,1,,,,,,,,,,《理論計算機科學基礎》,20,語法分析樹,文法G1: A ? 0A1 A ? B B ? #派生: A

11、? 0A1 ? 00A11 ? 000A111 ? 000B111語法分析樹,A,A,A,A,B,0,0,0,1,1,1,,,,,,,,,,,《理論計算機科學基礎》,21,語法分析樹,文法G1: A ? 0A1 A ? B B ? #派生: A ? 0A1 ? 00A11 ? 000A111 ? 000B111 ? 000#11

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

13、 A ? 0A1 A ? B B ? #縮寫: G1: A ? 0A1 | B B ? #,《理論計算機科學基礎》,24,G2, ? ? | ? | ? ? ? | ? a_ | the_ ? boy_ | gir

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

15、wer_likes_the_boy_,《理論計算機科學基礎》,27,G2, ? ? ? ? a_ ? a_boy_ ? a_boy_ ? a_boy_ ? a_boy_sees_,上下文無關文法的定義,,《理論計算機科學基礎》,28,《理論計算機科學基礎》,29,

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

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

18、礎》,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_ }, ),《理論計算機科學基礎》,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)包含所有匹配的括號串 或空串.,

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

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

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

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

24、礎》,43,合并CFG,為 {w|w=0n1n或w=1n0n,n?0} 設計CFG.為{w|w=0n1n,n?0}設計CFG.G1=({S1},{0,1},{S1?0S11,S1??},S1)為{w|w=1n0n,n?0}設計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),《理論計算機科學基礎》,44,合并CFG,一般情況: 增加 S?S1 | S2 |…| Sk S是新的初始變元S1, S2, …, Sk 是原來的初始變元,《理論計算機科學基礎》,45,合并CFG,一般情況: 增加 S?S1 | S2 |…| Sk S是新的初始變元S1, S2, …, Sk 是原來的初始變元定理: CFL對并運算封閉. #,《理論計算機科學基礎》,46,正則

26、語言,為正則語言設計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)Q={q0,q1,

27、…,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)Ri?aRj,,《理論計算機科學基礎》,51,正則語言,為正則語言設計CFG.把DFA轉換成等價的CFG設DFA M=(Q,?,?,q0,F)qi?F則CFG

28、 G=(V,?,R,R0)Ri??,《理論計算機科學基礎》,52,正則語言,為正則語言設計CFG.把DFA轉換成等價的CFG設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??定理: 正則語言都是 上下文無關語言.,《理論計算機科學基礎》,53,某些匹配,0n1

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

30、,58,某些匹配,wwR倒置: w=11010, wR=01011 可用上下文無關文法生成,《理論計算機科學基礎》,59,某些匹配,wwR倒置: w=11010, wR=01011 可用上下文無關文法生成ww,《理論計算機科學基礎》,60,某些匹配,wwR倒置: w=11010, wR=01011上下文無關ww非正則, 非上下文無關,《理論計算機科學基礎》,61,某些匹配,wwR倒置: w=11010, wR=010

31、11上下文無關ww非正則, 非上下文無關非ww,《理論計算機科學基礎》,62,某些匹配,wwR倒置: w=11010, wR=01011上下文無關ww非正則, 非上下文無關非ww上下文無關,《理論計算機科學基礎》,63,遞歸結構,(a+a)?a((a+a)+a)?a,+,a,),?,a,a,(,,,,,,,,,,,,,,,,,,,,,,,,,,,,,文法的歧義性,,《理論計算機科學基礎》,64,《理論計算機科學基礎

32、》,65,歧義性,G5: ? + | ? | () | a,《理論計算機科學基礎》,66,不同的分析樹,,,,a,+,a,?,a,,,,,,,,,,,,,,,a,?,a,,,,,,a,+,,,,,,,,《理論計算機科學基礎》,67,不同的結構與不同的意義,G2:the_girl_touches_the_boy_with_flower,《理論計算機科學基礎》,6

33、8,最左派生,最左派生: 每一步都替換最左邊的變元,《理論計算機科學基礎》,69,最左派生的例子, ? + ? a+ ? a+? ? a+a? ? a+a?a,《理論計算機科學基礎》,70,兩個不同的最左派生, ? + ? a+ ? a+? ? a+a? ? a+a?a ? ? ? + ? ? a+? ? a+a? ? a+a?a,《理論計算機科學基礎》,71,歧義

34、性地產生,最左派生: 每一步都替換最左邊的變元歧義地產生: 有兩個不同的最左派生,《理論計算機科學基礎》,72,歧義文法,最左派生: 每一步都替換最左邊的變元歧義地產生: 有兩個不同的最左派生歧義文法: 文法歧義地產生某個串,《理論計算機科學基礎》,73,固有歧義性,最左派生: 每一步都替換最左邊的變元歧義地產生: 有兩個不同的最左派生歧義文法:

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

36、ty)非確定性 (Nondeterminism),喬姆斯基范式的定義,,《理論計算機科學基礎》,76,《理論計算機科學基礎》,77,喬姆斯基范式(CNF),CNF: 只允許如下形式的規(guī)則: S??A?BCA?a其中A,B,C是任意變元B,C不是初始變元 (初始變元不能在右方出現(xiàn)) a是任意終結符,求喬姆斯基范式的算法,,《理論計算機科學基礎》,78,《理論計算機科學基礎》,79,喬姆斯基范式(CNF),等價:

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

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

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

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

41、成A?Bui可以證明，這樣求出的是等價的喬姆斯基范式 ， 定理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 |

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

43、 ? 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 ?

44、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,《理論計算機科學基礎》

45、,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

46、 | 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

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

48、| 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

49、,《理論計算機科學基礎》,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,例

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,《理論計算機科學基礎》,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,《理論計算機科學基

52、礎》,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,《理論計算機科學基礎》,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,《理論計算機科學基礎》,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,下推自動機的例子,,《理論計算機科學基礎》,106,《理論計算機科學基礎》,

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

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

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

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

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

60、接受狀態(tài)(終結狀態(tài))集,《理論計算機科學基礎》,118,PDA計算的形式定義,M=(Q,?,?,?,q0,F); 輸入w=w1w2…wm, wi???計算: 狀態(tài)-棧符號串序列 (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??*,《理論計算機科學基礎》,119,PDA計算的形式定義,接受計算:3) rm?F; (或者同時要求sm=?)M接受w: M對輸入w存在接受計算M(識別,接受)的語言: L(M) = { x | M接受x },下推自動機的例子,,《理論計算機科學基礎》,120,《理論計算機科學基礎》,121,例3.9,L(M1)={ 0n1n | n?

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

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

64、讀到一個輸入符號c, 就從堆棧中彈出一個a, 若輸入結束時 堆棧排空,則接受;否則拒絕,《理論計算機科學基礎》,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,,《理論計算機科學基礎》,127,例3.11,L(M3)={ wwR | w?{0,1}* },《理論計算機科學基礎》,128,例3.11,L(M3)={ wwR | w?{0,1}* }開始時,把讀到的符號推入堆棧中在每一步,非確定性地猜測已到達 字符串的中點,然后變成把讀到的每一個符號彈出堆棧, 檢查在輸入中和在堆棧頂 讀到的符號是否一樣如果它們總是一樣的, 并且輸入結束時堆棧同時排空

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