形式語言與自動機(jī)理論--第二章 文法-3（第五周）

1、第2章 文法 1.語言結(jié)構(gòu)分析2.文法形式定義3.文法的構(gòu)造4.文法的喬姆斯基體系5.空語句6.小結(jié)14.文法的喬姆斯基體系定義2-7 線性文法(liner grammar) 設(shè)G=(V，T，P，S)，如果對于P，均具有如下形式：AwAwBx其中A，BV，w，xT*，則稱G為線性文法。線性語言(liner language) L(G)叫做線性語言24.文法的喬姆斯基體系定義2-8 右線性文法(right liner grammar) 設(shè)G=(V，T，P，S)，如果對于P，均具有如下形式：AwAwB其中A，BV，wT+，則稱G為右線性文法。右線性文法就是RG右線性語言(right liner l

2、anguage) L(G)叫做右線性語言。34.文法的喬姆斯基體系左線性文法(left liner grammar) 設(shè)G=(V，T，P，S)，如果對于P，均具有如下形式：AwABw其中A，BV，wT+，則稱G為左線性文法。左線性語言(left liner language) L(G)叫做左線性語言。44.文法的喬姆斯基體系定理2-2 L是一個左線性語言的充要條件是存在文法G，G中的產(chǎn)生式要么是形如：Aa的產(chǎn)生式，要么是形如ABa的產(chǎn)生式，使得L(G)=L。其中A、B為語法變量，a為終極符號。 54.文法的喬姆斯基體系定理2-3 左線性文法與右線性文法等價。 按照定理2-1的證明經(jīng)驗(yàn)，要想證明

3、本定理，需要完成如下工作：對任意右線性文法G，我們能夠構(gòu)造出對應(yīng)的左線性文法G，使得L(G)=L(G)；對任意左線性文法G，我們能夠構(gòu)造出對應(yīng)的右線性文法G，使得L(G)=L(G)。64.文法的喬姆斯基體系例 2-17 語言0123456的左線性文法和右線性文法的構(gòu)造。右線性文法Gr：Sr0ArAr1BrBr2CrCr3DrDr4ErEr5FrFr6 74.文法的喬姆斯基體系0123456在文法Gr中的推導(dǎo) Sr0Ar使用產(chǎn)生式Sr0Ar 01Br使用產(chǎn)生式Ar1Br 012Cr 使用產(chǎn)生式Br2Cr 0123Dr 使用產(chǎn)生式Cr3Dr 01234Er使用產(chǎn)生式Dr4Er 012345Fr使用

4、產(chǎn)生式Er5Fr 0123456使用產(chǎn)生式Fr684.文法的喬姆斯基體系左線性文法Gl：SlAl6 AlBl5 BlCl4 ClDl3 DlEl2 ElFl1 Fl0 94.文法的喬姆斯基體系104.文法的喬姆斯基體系0123456在文法Gl中的推導(dǎo) SlAl6使用產(chǎn)生式SlAl6 Bl56使用產(chǎn)生式AlBl5 Cl456使用產(chǎn)生式BlCl4 Dl3456使用產(chǎn)生式ClDl3 El23456 使用產(chǎn)生式DlEl2 Fl1234456使用產(chǎn)生式ElFl1 0123456使用產(chǎn)生式Fl0 114.文法的喬姆斯基體系0123456被歸約成文法Gl的開始符號S 0123456 Fl1234456使用產(chǎn)

5、生式Fl0 El23456使用產(chǎn)生式ElFl1 Dl3456使用產(chǎn)生式DlEl2 Cl456使用產(chǎn)生式ClDl3 Bl56使用產(chǎn)生式BlCl4 Al6使用產(chǎn)生式AlBl5 Sl使用產(chǎn)生式SlAl6 124.文法的喬姆斯基體系134.文法的喬姆斯基體系定理 2-4 左線性文法的產(chǎn)生式與右線性文法的產(chǎn)生式混用所得到的文法不是RG。證明：設(shè)有文法G15：S0AAS1|1 不難看出，L(G15)=0n1n|n1。我們構(gòu)造不出RG G，使得L(G)= L(G15)=0n1n|n1。因?yàn)長(G15)=0n1n|n1不是RL。所以，G15不是RG。有關(guān)該語言不是RL的證明我們將留到研究RL的性質(zhì)時去完成。

6、145. 空語句 形如A的產(chǎn)生式叫做空產(chǎn)生式，也可叫做產(chǎn)生式。 在RG、CFG、CSG中，都不能含有空產(chǎn)生式。所以，任何CSL中都不含有空語句。從而CFL和RL中都不能含空語句。 空語句在一個語言中的存在并不影響該語言的有窮描述的存在性，甚至除了為生成空語句外，空產(chǎn)生式可以不被用于語言中其他任何句子的推導(dǎo)中。 155. 空語句 允許CSL、CFL、RL包含空語句后，還會給問題的處理提供一些方便。 允許在RG、CFG、CSG中含有空產(chǎn)生式允許CSL、CFL、RL包含空語句。 165. 空語句 定理2-5 設(shè)G=(V，T，P，S)為一文法，則存在與G同類型的文法G=(V，T，P，S)，使得L(G)

7、=L(G)，但G的開始符號S不出現(xiàn)在G的任何產(chǎn)生式的右部。證明：（1）當(dāng)文法G=(V，T，P，S)的開始符號S不出現(xiàn)在P中的任何產(chǎn)生式的右部時，G就是所求的G175. 空語句 （2）如果不滿足（1）的情況，則取S V，G=(VS，T，P，S) 其中 P=PS|SP 上述文法滿足定義要求的G，只需證明在“但G的開始符號S不出現(xiàn)在G的任何產(chǎn)生式的右部”條件下， L(G)= L(G) 分析：如果L(G) L(G) 且L(G) L(G) 則L(G)= L(G) 所以分別證明L(G) L(G) 和L(G) L(G) 均成立即可。185. 空語句 （1）證明L(G) L(G)思路：如果對于任意的xL(G)

8、 都能證明xL(G)，則 L(G) L(G)成立證明：對任意的xL(G)，由文法產(chǎn)生的語言的定義知，在G中存在如下推導(dǎo)： S 使用產(chǎn)生式S（根據(jù)定理，S僅在產(chǎn)生式左側(cè)出現(xiàn)，所以由推導(dǎo)出x必定通過P中的除S以外的其他產(chǎn)生式產(chǎn)生的，即 *x 195. 空語句 因?yàn)镻=PS|SP 所以推導(dǎo)*x中使用的產(chǎn)生式都是P中的產(chǎn)生式。因此，推導(dǎo)*x在G中仍然成立。由P的定義知，必有SP 所以， S使用P中的產(chǎn)生式S *x使用P中的產(chǎn)生式 故，x L(G) 所以： L(G)L(G) 成立205. 空語句 （2）證明 L(G)L(G)對任意的xL(G)，G中存在如下推導(dǎo)： S使用P中的產(chǎn)生式S *x使用P中的產(chǎn)生

9、式由P=PS|SP ，知道G中， S使用產(chǎn)生式S *x使用P所包含的P中的其他產(chǎn)生式。 故， x L(G)所以L(G)L(G)。 綜上，定理得到證明。215. 空語句 定義2-10：設(shè)G=(V，T，P，S)是一個文法，如果S不出現(xiàn)在G的任何產(chǎn)生式的右部，則： 如果G是CSG，則仍然稱G=(V，T，PS，S)為CSG；G產(chǎn)生的語言仍然稱為CSL。 如果G是CFG，則仍然稱G=(V，T，PS，S)為CFG；G產(chǎn)生的語言仍然稱為CFL。 如果G是RG，則仍然稱G=(V，T，PS，S)為RG。G產(chǎn)生的語言仍然稱為RL。225. 空語句 定理2-6 下列命題成立： 如果L是CSL，則L仍然是CSL。 如

10、果L是CFL，則L仍然是CFL。 如果L是RL，則L仍然是RL。235. 空語句 證明：對第1個命題：設(shè)L是CSL，則存在一個CSG G=(V，T，P，S)，使得L(G)=L。由定理2-5-1，不妨假設(shè)S不出現(xiàn)在G的任何產(chǎn)生式的右部。?。篏=(V，T，PS，S)由于S不出現(xiàn)在G的任何產(chǎn)生式的右部，所以，S不可能出現(xiàn)在任何長度不為0的句子的推導(dǎo)中。245. 空語句 易證：L(G)=L(G)。由于G是CSG，所以，L(G)是CSL。同理可證第2和第3個命題。 255. 空語句 定理2-7 下列命題成立 如果L是CSL，則L-仍然是CSL。 如果L是CFL，則L-仍然是CFL。 如果L是RL，則L-

11、仍然是RL。 265. 空語句 證明：對第1個命題：設(shè)L是CSL，則存在一個CSG G=(V，T，P，S)，使得L(G)=L。如果L，則L-=L，所以， L-是CSL。如果L，由定理2-5，不妨假設(shè)S不出現(xiàn)在G的任何產(chǎn)生式的右部。?。篏=(V，T，P-S，S)275. 空語句 由于S不出現(xiàn)在G的任何產(chǎn)生式的右部，所以，如果L(G)中存在長度非0的句子，S不可能出現(xiàn)在它們的推導(dǎo)中。也就是說，將S從G中去掉后，不會影響L(G)中任何長度非0的句子的推導(dǎo)。容易證明： L(G)=L(G)-由于G是CSG，所以，L(G)-是CSL。同理可證其他兩個命題。 285. 空語句 對于任意文法G=(V，T，P，

12、S)，對于G中的其他變量A，出現(xiàn)形如A的產(chǎn)生式是不會改變文法產(chǎn)生的語言的類型的，而且這樣一來，對我們進(jìn)行文法的構(gòu)造等工作還提供了很多方便。所以，我們約定：對于G中的任何變量A，在需要的時候，可以出現(xiàn)形如A的產(chǎn)生式。 296. 小結(jié) 本章討論了語言的文法描述。首先介紹文法的基本定義和推導(dǎo)、歸約、文法定義的語言、句子、句型、文法的等價等重要概念。 討論了如何根據(jù)語言的特點(diǎn)、通過用語法變量去表示適當(dāng)?shù)募希ㄕZ法范疇）的方法進(jìn)行文法構(gòu)造， 介紹了文法的喬姆斯基體系，將文法劃分成PSG、CSG、CFG、RG等4類。 在這些文法中，線性文法是一類重要的文法。 306. 小結(jié) 文法G=(V，T，P，S)。任意AV表示集合L(A)=w | wT*且A * w。 推導(dǎo)與歸約。文法中的推導(dǎo)是根據(jù)文法的產(chǎn)生式進(jìn)行的。如果P，(VT)*，則稱在G中直接推導(dǎo)出：G ；也稱在文法G中直接歸約成。316. 小結(jié) 語言、句子和句型。文法G產(chǎn)生的語言L(G)=w | wT*且S * w，