自動(dòng)機(jī)第三章

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

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

3、謝謝觀賞 L2=anbncmdm|n,m=1中的串可以看作是由兩種串a(chǎn)nbn (n=1)和 cmdm(m=1)連接而成。為此，我們只要從初始符S產(chǎn)生出兩個(gè)變量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)文法和語(yǔ)言歧義性固有歧義引理謝謝觀賞對(duì)于L3=anbmcmdn|n,m=1中的串，則要把他們看做是bmcm和andn的嵌套，其中bmcm在內(nèi)層

4、，andn在外層。因此我們可以設(shè)置一個(gè)變量（如初始符S）生成andn（n1），重復(fù)（任意的）若干次后，用另一個(gè)變量取代初始符，新的變量再生成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)文法和語(yǔ)言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子第一部分第二部分第三部分第四部分第五部分上下文無關(guān)文法和語(yǔ)言歧義性固有歧義引理謝謝觀賞定 義Bullet point 2例 子設(shè)G=（V,T;P,S）為

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

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

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

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