自動機第三章

1、第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2例 子定 義Bullet point 2定 義第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 1定 義Bullet point 1定 義Bullet point 2定 義Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞定 義任何由上下文無關(guān)文法生成的語言，稱之為上下文無關(guān)語言(CFL)定 義第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語

2、言歧義性固有歧義引理謝謝觀賞Bullet point 1定 義Bullet point 2例 子Bullet point 2例 子分別構(gòu)造出產(chǎn)生下列3個語言的上下文無關(guān)文法： L1=anbn|n=1 L2=anbncmdm|n,m=1 L3=anbmcmdn|n,m=1易知：L1中最短的串是ab，如果w是L1中的一個串，那么awb仍然是L1中的串，而且L1中的串都可以由此生成。這樣我們就得到 G1=(S,a,b;P1,S) P1:SaSb|ab這樣就有 L( G1)=anbn|n=1Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理

3、謝謝觀賞 L2=anbncmdm|n,m=1中的串可以看作是由兩種串a(chǎn)nbn (n=1)和 cmdm(m=1)連接而成。為此，我們只要從初始符S產(chǎn)生出兩個變量A和B連接，然后由變量A生成anbn由變量B生成 cmdm，就可以產(chǎn)生出 L2。即G2=(S,A,B,a,b,c,d;P2,S)P2：SABAaAb|abBcBd|cd這樣就有 L(G2)=anbncmdm|n,m1Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞對于L3=anbmcmdn|n,m=1中的串，則要把他們看做是bmcm和andn的嵌套，其中bmcm在內(nèi)層

4、，andn在外層。因此我們可以設(shè)置一個變量（如初始符S）生成andn（n1），重復（任意的）若干次后，用另一個變量取代初始符，新的變量再生成bmcm（m1），即G3=(S,A,a,b,c,d;P3,S)P3:SaSd|aAd AbAc|bc這樣就有 L(G3)=anbmcmdn|n,m1Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子設(shè)G=（V,T;P,S）為

5、一個上下文無關(guān)文法。若存在x L(G),使得有兩個（或兩個以上）不同的推導樹產(chǎn)生x，則稱G為一個有歧義的文法?；蚝喎QG為一個歧義文法 。定 義第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子設(shè)有一個上下文無關(guān)文法G1=（S,A,B,a,b;P1,S） P1: S-SA|SB|a A-b B-b對于文法G1的一個推導樹：圖1所示的推導樹對應的一個推導式：SSBaBab圖2所示的推導樹對應的推導式：SSAaAabSSASbab圖1與圖2是兩個不同的推導樹都產(chǎn)生了ab，所以G為一個有歧義的文法。Bullet point 2

6、例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義設(shè)L為一個上下文無關(guān)語言。如果產(chǎn)生L的每一個上下文無關(guān)文法都是歧義文法，則稱L為一個固有歧義的上下文無關(guān)文法。定 義第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義Bullet point 2證 明Bullet point 2證 明第一部分第二部分第三部分第四部分

7、第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明當n=m時 anbncndn 形的串既可以通過SAB推導過程得到也可以通過SC 推導過程得到。顯然，這兩個推導過程對應的推導樹不相同，所以這個文法G是有歧義的。這僅僅是證明了這個文法是有歧義的，但無法證明其它可以產(chǎn)生L語言的文法是有歧義的，所以暫時無法定下結(jié)論： L是固有歧義性的 第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point

8、 23.43.3證明證明第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 23.43.33.3證明證明第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 23.43.3Bullet point 23.4證明證明第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 23.43.3從3.3節(jié)知，在一個CFG中消去無用符號、空產(chǎn)生式以及單產(chǎn)生式的過程不會影響一個文法的歧義性。所以假設(shè)G中沒有無用符號和無用產(chǎn)生式先假設(shè)G中有個非初始變量A（AS），A不存在一個推導 Ax Ax （x ，x T*且x