自動機第三章

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

2、言歧義性固有歧義引理謝謝觀賞Bullet point 1定 義Bullet point 2例 子Bullet point 2例 子分別構造出產(chǎn)生下列3個語言的上下文無關文法： 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例 子第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理

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例 子第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞對于L3=anbmcmdn|n,m=1中的串，則要把他們看做是bmcm和andn的嵌套，其中bmcm在內層

4、，andn在外層。因此我們可以設置一個變量（如初始符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例 子第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子設G=（V,T;P,S）為

5、一個上下文無關文法。若存在x L(G),使得有兩個（或兩個以上）不同的推導樹產(chǎn)生x，則稱G為一個有歧義的文法?；蚝喎QG為一個歧義文法 。定 義第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子設有一個上下文無關文法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、例 子第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義設L為一個上下文無關語言。如果產(chǎn)生L的每一個上下文無關文法都是歧義文法，則稱L為一個固有歧義的上下文無關文法。定 義第一部分第二部分第三部分第四部分第五部分上下文無關文法和語言歧義性固有歧義引理謝謝觀賞Bullet point 2證 明定 義Bullet point 2證 明Bullet point 2證 明第一部分第二部分第三部分第四部分

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

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