形式語言與自動機理論--第二章 文法-2（第四周）

1、第第2章章 文法文法 1.1.語言結(jié)構(gòu)分析語言結(jié)構(gòu)分析2.2.文法形式定義文法形式定義3.3.文法的構(gòu)造文法的構(gòu)造4.4.文法的喬姆斯基體系文法的喬姆斯基體系5.5.空語句空語句6.6.小結(jié)小結(jié)13.文法的構(gòu)造文法的構(gòu)造 例例 2-10L=0n|n1 G6：S0|0S L=0n|n0 G7：S|0SL=02n13n|n0 G8：S|00S11123.文法的構(gòu)造文法的構(gòu)造 例例2-11 構(gòu)造文法構(gòu)造文法G9，使，使L(G9)=w|wa，b，z+。 G9：SA|AS Aa|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 用用SA|AS生成生成 A

2、n。 不可以用不可以用Aa|b|c|z表示表示Aa|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不可以用不可以用Aa8表示表示Aaaaaaaaa。不能用不能用Aan表示表示A可以產(chǎn)生任意多個可以產(chǎn)生任意多個a。 33.文法的構(gòu)造文法的構(gòu)造 例例2-12 構(gòu)造文法構(gòu)造文法G10，使，使L(G10)=wwT|w0，1，2，3+。 文法文法SHEH0|1|2|3|0H|1H|2H|3HE0|1|2|3|E0|E1|E2|E3難以生成難以生成L(G10)。43.文法的構(gòu)造文法的構(gòu)造 wwT|w0，1，2，3+的句子的特點的句子的特點 設(shè)設(shè)w=a1a

3、2an，從而有，從而有wT= ana2 a1，故故 wwT= a1a2anana2 a1 滿足滿足f(w wT，i)=f(w wT，|w wT|-i+1)。 遞歸地定義遞歸地定義L 對對 a0，1，2，3，aaL； 如果如果xL，則對，則對 a0，1，2，3，axaL； L中不含不滿足中不含不滿足(1)、(2)任何其他的串。任何其他的串。 53.文法的構(gòu)造文法的構(gòu)造 根據(jù)遞歸定義中的第一條，有如下產(chǎn)生式組：根據(jù)遞歸定義中的第一條，有如下產(chǎn)生式組：S00 | 11 | 22 | 33再根據(jù)遞歸定義第二條，又可得到如下產(chǎn)生式組：再根據(jù)遞歸定義第二條，又可得到如下產(chǎn)生式組：S0S0 | 1S1 |

4、2S2 | 3S3從而，從而，G10：S00 | 11 | 22 | 33 | 0S0 | 1S1 | 2S2 | 3S3 63.文法的構(gòu)造文法的構(gòu)造 例例2-13 構(gòu)造文法構(gòu)造文法G12，使，使L(G12)=w|w是十進制有理數(shù)是十進制有理數(shù)。設(shè)設(shè)S為開始符號，無符號有理數(shù)表示為為開始符號，無符號有理數(shù)表示為R則可得到產(chǎn)生式：則可得到產(chǎn)生式：SR | +R | -RR又可以劃分為整數(shù)（又可以劃分為整數(shù)（N）、帶小數(shù)（整數(shù)部分不為）、帶小數(shù)（整數(shù)部分不為0：B）和純）和純小數(shù)（整數(shù)部分為小數(shù)（整數(shù)部分為0：P），即得到產(chǎn)生式：），即得到產(chǎn)生式：RN | B | P帶小數(shù)是有帶小數(shù)是有“.”隔開

5、的整數(shù)部分和小數(shù)部分組成，其中整數(shù)部隔開的整數(shù)部分和小數(shù)部分組成，其中整數(shù)部分就是無符號整數(shù)分就是無符號整數(shù)N，小數(shù)部分用，小數(shù)部分用D表示，即得到產(chǎn)生式：表示，即得到產(chǎn)生式： BN.D純小數(shù)產(chǎn)生式為：純小數(shù)產(chǎn)生式為： P0.D73.文法的構(gòu)造文法的構(gòu)造 對于無符號有理數(shù)對于無符號有理數(shù)N，對應(yīng)字母表，對應(yīng)字母表0,1,2,3,4,5,6,7,8,9上的語言，但是如果上的語言，但是如果N為個位數(shù)，為個位數(shù)，可以為可以為1-9任意一個，如果任意一個，如果N為兩位數(shù)，則十位數(shù)字為兩位數(shù)，則十位數(shù)字不應(yīng)該為不應(yīng)該為0，如果，如果N為百位數(shù)，則百位數(shù)不應(yīng)該為為百位數(shù)，則百位數(shù)不應(yīng)該為0，總結(jié)，即對于非

6、個位數(shù)來說，總結(jié)，即對于非個位數(shù)來說，N的最高位不應(yīng)該為的最高位不應(yīng)該為0，所以考慮構(gòu)造以下產(chǎn)生式來滿足以上要求：，所以考慮構(gòu)造以下產(chǎn)生式來滿足以上要求：N 0|AMA 1| 2 | 3| 4| 5 | 6| 7| 8 | 9M| 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M（代表字母表（代表字母表0,1,2,3,4,5,6,7,8,9上生成的所有句子）上生成的所有句子）83.文法的構(gòu)造文法的構(gòu)造 對于小數(shù)部分對于小數(shù)部分D，要求與，要求與N正好相反，小數(shù)部分為正好相反，小數(shù)部分為0，或者最低位小數(shù)位不能為，或者最低位小數(shù)位不能為0，按照以上要

7、求得，按照以上要求得到產(chǎn)生式：到產(chǎn)生式：D 0|MAA 1| 2 | 3| 4| 5 | 6| 7| 8 | 9M| 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M（代表字母表（代表字母表0,1,2,3,4,5,6,7,8,9上生成的所有句子）上生成的所有句子）93.文法的構(gòu)造文法的構(gòu)造 將上述產(chǎn)生式整理到一起，得到十進制有理數(shù)文法表示將上述產(chǎn)生式整理到一起，得到十進制有理數(shù)文法表示為：為： SR | +R | -RRN | B|PBN.D P 0.DN0 | AMD0 | MAA1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

8、 M| 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M103.文法的構(gòu)造文法的構(gòu)造 由于由于N可以推導(dǎo)出可以推導(dǎo)出0，所以，所以P 0.D包含在包含在BN.D產(chǎn)生式產(chǎn)生式中，可以去掉與中，可以去掉與P有關(guān)的產(chǎn)生式，得到十進制有理數(shù)文有關(guān)的產(chǎn)生式，得到十進制有理數(shù)文法表示為：法表示為：G12：SR | +R | -RRN | BBN.DN0 | AMD0 | MAA1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 M| 0M | 1M | 2M | 3M | 4M | 5M | 6M | 7M | 8M | 9M113.文法的構(gòu)造

9、文法的構(gòu)造 例例2-14 構(gòu)造產(chǎn)生算術(shù)表達式的文法：構(gòu)造產(chǎn)生算術(shù)表達式的文法： 基礎(chǔ)：常數(shù)是算術(shù)表達式，變量是算術(shù)表達基礎(chǔ)：常數(shù)是算術(shù)表達式，變量是算術(shù)表達式；式； 歸納：如果歸納：如果E1、E2是表達式，則是表達式，則 +E1、-E1、E1+E2、 E1-E2 、E1*E2 、E1/E2、E1*E2、Fun(E1)是算術(shù)表達式。其中是算術(shù)表達式。其中Fun為函數(shù)名。為函數(shù)名。 只有滿足只有滿足(1)和和(2)的才是算術(shù)表達式。的才是算術(shù)表達式。 G13：Eid|c|+E|-E|E+E|E-E|E*E|E/E|E*E|Fun(E) 12 3.文法的構(gòu)造文法的構(gòu)造例例2-15 構(gòu)造產(chǎn)生語言構(gòu)造產(chǎn)

10、生語言anbncn|n1的文法。的文法。 文法文法G=(S1，a，b，S1ab | aS1b，S1)產(chǎn)生的語言產(chǎn)生的語言anbn | n1形式上看起來與語言形式上看起來與語言anbncn | n1比較接近。比較接近。G=(S2，c，S2c | cS2，S2)產(chǎn)生的語言是產(chǎn)生的語言是cn|n1。anbncn | n1anbn | n1cn | n1 133.文法的構(gòu)造文法的構(gòu)造文法文法SS1S2S1ab | aS1bS2c | cS2 不能產(chǎn)生語言不能產(chǎn)生語言anbncn | n1 而是產(chǎn)生語言而是產(chǎn)生語言 an nbn n | n1cn n | n1 143.文法的構(gòu)造文法的構(gòu)造文法文法G：S

11、abc | aSbc 產(chǎn)生的語言為：產(chǎn)生的語言為：an(bc)n | n1 焦點：交換焦點：交換b和和c的位置。的位置。153.文法的構(gòu)造文法的構(gòu)造G14：SaBC | aSBC， CBBC aBab bBbb bCbc cCccG14：Sabc|aSBc， bBbb cBBc 164.文法的喬姆斯基體系文法的喬姆斯基體系定義定義2-6(1)2-6(1)文法文法G=(V，T，P，S) G叫做叫做0型文法型文法(type 0 grammar)，也叫做短語結(jié)構(gòu)文，也叫做短語結(jié)構(gòu)文法法(phrase structure grammar, PSG)。L(G)叫做叫做0型語言。也可以叫做短語結(jié)構(gòu)語言型語

12、言。也可以叫做短語結(jié)構(gòu)語言(PSL)、遞歸可枚舉集遞歸可枚舉集(recursively enumerable ，r.e. )。 174.文法的喬姆斯基體系文法的喬姆斯基體系定義定義2-6(2)2-6(2)G G是是0 0型文法。型文法。如果對于如果對于 P，均有，均有|成立，則稱成立，則稱G為為1型文法型文法(type 1 grammar)，或上下文有關(guān)文法，或上下文有關(guān)文法(context sensitive grammar,CSG)。L(G)叫做叫做1型語言型語言(type 1 language)或者上下文有或者上下文有關(guān)語言關(guān)語言(context sensitive language ,

13、CSL)。184.文法的喬姆斯基體系文法的喬姆斯基體系定義定義2-6(3)2-6(3)G是是1型文法型文法如果對于如果對于 P，均有，均有|，并且，并且V成立，則稱成立，則稱G為為2型文法型文法(type 2 grammar)，或上下文無關(guān)文法，或上下文無關(guān)文法(context free grammar,CFG)。L(G)叫做叫做2型語言型語言(type 2 language)或者上下文無關(guān)語言或者上下文無關(guān)語言(context free language ,CFL)。 194.文法的喬姆斯基體系文法的喬姆斯基體系定義定義2-6(4)2-6(4)G是是2型文法型文法如果對于如果對于 P，均具有

14、形式均具有形式 Aw AwB其中其中A，BV，wT+。則稱。則稱G為為3型文法型文法(type 3 g r a m m a r ) ， 也 可 稱 為 正 則 文 法， 也 可 稱 為 正 則 文 法 ( r e g u l a r grammar ,RG)或者正規(guī)文法?；蛘哒?guī)文法。L(G)叫做叫做3型語言型語言(type 3 language)，也可稱為正則，也可稱為正則語言或者正規(guī)語言語言或者正規(guī)語言(regular language ,RL)。 204.文法的喬姆斯基體系文法的喬姆斯基體系舉例：舉例：G1:S0|1|0A|1B,A0,B1 (0,1,2,3)G2:S00|11|22|3

15、3|0S0|1S1|2S2|3S3 (0,1,2)G3: SaBC|aSBC (0,1) CB BC aBab bBbb bCbc cCccG4: SA|B|BB,A0,B1,CACS21,C11,C2(0) 214.文法的喬姆斯基體系文法的喬姆斯基體系 如果一個文法如果一個文法G是是RG，則它也是，則它也是CFG、CSG和短和短語結(jié)構(gòu)文法。反之不一定成立。語結(jié)構(gòu)文法。反之不一定成立。 如果一個文法如果一個文法G是是CFG，則它也是，則它也是CSG和短語結(jié)和短語結(jié)構(gòu)文法。反之不一定成立。構(gòu)文法。反之不一定成立。 如果一個文法如果一個文法G是是CSG，則它也是短語結(jié)構(gòu)文法。，則它也是短語結(jié)構(gòu)文法

16、。反之不一定成立。反之不一定成立。相應(yīng)地：相應(yīng)地： RL也是也是CFL、CSL和短語結(jié)構(gòu)語言。反之不一定和短語結(jié)構(gòu)語言。反之不一定成立。成立。224.文法的喬姆斯基體系文法的喬姆斯基體系 CFL也是也是CSL和短語結(jié)構(gòu)語言。反之不一定成立。和短語結(jié)構(gòu)語言。反之不一定成立。 CSL也是短語結(jié)構(gòu)語言。反之不一定成立也是短語結(jié)構(gòu)語言。反之不一定成立 當(dāng)文法當(dāng)文法G是是CFG時，時，L(G)卻可以是卻可以是RLRL。 當(dāng)文法當(dāng)文法G是是CSG時，時，L(G)可以是可以是RL、CSL。 當(dāng)文法當(dāng)文法G是短語結(jié)構(gòu)文法時，是短語結(jié)構(gòu)文法時，L(G)可以是可以是RL、CSL和和CSL。 234.文法的喬姆斯基

17、體系文法的喬姆斯基體系定理定理 2-1 L是是RL的充要條件是存在一個文法，該文法的充要條件是存在一個文法，該文法產(chǎn)生語言產(chǎn)生語言L，并且它的產(chǎn)生式要么是形如：，并且它的產(chǎn)生式要么是形如：Aa的產(chǎn)的產(chǎn)生式，要么是形如生式，要么是形如AaB的產(chǎn)生式。其中的產(chǎn)生式。其中A、B為語法為語法變量，變量，a為終極符號。為終極符號。 證明證明 ：充分性：充分性：即需要證明滿足定理中闡述的文法規(guī)則的文法即需要證明滿足定理中闡述的文法規(guī)則的文法生成的語言是生成的語言是RLRL。設(shè)有設(shè)有G，L(G)=L，且，且G的產(chǎn)生式的形式滿足定理的產(chǎn)生式的形式滿足定理要求。這種文法就是要求。這種文法就是RG。所以，。所以，

18、G產(chǎn)生的語言就是產(chǎn)生的語言就是RL，故，故L是是RL。 244.文法的喬姆斯基體系文法的喬姆斯基體系必要性必要性 ：即需要證明如果一個語言是即需要證明如果一個語言是RL，則必定存，則必定存在一個文法，其文法規(guī)則滿足定理要求。在一個文法，其文法規(guī)則滿足定理要求。思路：假設(shè)產(chǎn)生語言思路：假設(shè)產(chǎn)生語言RL的文法為的文法為RG，證明存在文法，證明存在文法G，G 滿足定理文法規(guī)則，且滿足定理文法規(guī)則，且L(G)=L(G)即可。即可。證明：證明：設(shè)設(shè)G=(V，T，P，S) 是是RG根據(jù)根據(jù)RG的定義，的定義，P中的產(chǎn)生式要么是形如中的產(chǎn)生式要么是形如Aw的，要么的，要么是形如是形如AwB的。的。為不失一般

19、性，設(shè)為不失一般性，設(shè)w=a1a2a3an，其中其中n1254.文法的喬姆斯基體系文法的喬姆斯基體系則，對于則，對于P中的每個產(chǎn)生式按照如下方法進行處理：中的每個產(chǎn)生式按照如下方法進行處理：對于形如對于形如A A a1a2a3an的產(chǎn)生式，引入新變量的產(chǎn)生式，引入新變量A1，A2，An-1，構(gòu)造：用構(gòu)造：用產(chǎn)生式組：產(chǎn)生式組：Aa1A1A1a2A2An-1an代替產(chǎn)生式代替產(chǎn)生式A a1a2an 將新生成的產(chǎn)生式放入產(chǎn)生式集將新生成的產(chǎn)生式放入產(chǎn)生式集P 中中264.文法的喬姆斯基體系文法的喬姆斯基體系對于形如對于形如A A a1a2a3anB的產(chǎn)生式，引入新變量的產(chǎn)生式，引入新變量A1，A2

20、，An-1，構(gòu)造：用構(gòu)造：用產(chǎn)生式組：產(chǎn)生式組：Aa1A1A1a2A2An-1anB代替產(chǎn)生式代替產(chǎn)生式A a1a2an B將新生成的產(chǎn)生式放入產(chǎn)生式集將新生成的產(chǎn)生式放入產(chǎn)生式集P 中中274.文法的喬姆斯基體系文法的喬姆斯基體系定義定義G =(V ，T，P ，S) 其中其中V = = V A1，A2，An-1 P = =Aa1A1,A1a2A2，An-1anB 即對所即對所有有P P中產(chǎn)生式進行變型后生成的產(chǎn)生式中產(chǎn)生式進行變型后生成的產(chǎn)生式按照如上定義，文法按照如上定義，文法G 符合定理符合定理2-12-1的文法規(guī)則的文法規(guī)則的要求的要求下面只需要證明下面只需要證明L(G)=L(G) 即

21、可。即可。284.文法的喬姆斯基體系文法的喬姆斯基體系證明證明L(G)=L(G) 。 思路思路1 1：由于由于P P中產(chǎn)生式中產(chǎn)生式A a1a2a3an的功能可以由產(chǎn)生式組的功能可以由產(chǎn)生式組Aa1A1A1a2A2An-1an來實現(xiàn)。來實現(xiàn)。294.文法的喬姆斯基體系文法的喬姆斯基體系P P中產(chǎn)生式中產(chǎn)生式A A a1a2a3anB 的功能可以由產(chǎn)生式組的功能可以由產(chǎn)生式組Aa1A1A1a2A2An-1anB來實現(xiàn)來實現(xiàn)在在P P中新定義的變量只有在中新定義的變量只有在P P中中“源產(chǎn)生式源產(chǎn)生式”推導(dǎo)時推導(dǎo)時才能用上，因此他們生成語言的能力是相同的，即才能用上，因此他們生成語言的能力是相同的

22、，即L(G)=L(G)304.文法的喬姆斯基體系文法的喬姆斯基體系證明證明L(G)=L(G) 。思路思路2 2：從數(shù)學(xué)推導(dǎo)角度對從數(shù)學(xué)推導(dǎo)角度對 L(G)=L(G)進行證明。進行證明。需要證明對于需要證明對于 x T T* *，x x L(G) x x L(G) 即，即， x T T* *，S S G+ x S G+ x為此，施歸納于推導(dǎo)的步數(shù)，證明一個更一般的結(jié)論：為此，施歸納于推導(dǎo)的步數(shù)，證明一個更一般的結(jié)論：對于對于 AV，A G+ xA G+ x。因為。因為SV，所以，所以結(jié)論自然對結(jié)論自然對S成立。成立。 314.文法的喬姆斯基體系文法的喬姆斯基體系 AV，A G+ xA G+ x(

23、1)(1)證明證明A G+ x A G+ x證明：采用歸納法進行證明證明：采用歸納法進行證明設(shè)設(shè)A Gn x （即從（即從A出發(fā)，經(jīng)過出發(fā)，經(jīng)過n步得到步得到x）當(dāng)當(dāng)n=1時，必存在時，必存在Ax P P 設(shè)設(shè)x=x= a1a2a3ah，根據(jù)，根據(jù)G的定義，由產(chǎn)生式組的定義，由產(chǎn)生式組Aa1A1A1a2A2Ah-1ah324.文法的喬姆斯基體系文法的喬姆斯基體系故以下推導(dǎo)過程成立：故以下推導(dǎo)過程成立：A Ga a1 1A A1 1 Ga a1 1a a2 2A A2 2 Ga a1 1a a22a ah-1h-1a ah h上述結(jié)論說明，在上述結(jié)論說明，在n=1時，時， A G x A Gx成

24、立成立設(shè)設(shè)n=k時結(jié)論成立，往證時結(jié)論成立，往證n=k+1時結(jié)論成立。時結(jié)論成立。334.文法的喬姆斯基體系文法的喬姆斯基體系設(shè)設(shè)n=k+1，x=x1x2，即，即A Gk+1x x1 1x2。引入變量引入變量B設(shè)設(shè) A Gx x1 1B B Gkx x1 1x x2 2( (先經(jīng)過先經(jīng)過1 1步推導(dǎo)，再經(jīng)過步推導(dǎo)，再經(jīng)過k k步推步推導(dǎo)）導(dǎo)）設(shè)設(shè)x x1 1= = a1a2a3ah即即A a1a2a3ahB PP根據(jù)根據(jù)G定義，定義，P中包含產(chǎn)生式組中包含產(chǎn)生式組Aa1A1A1a2A2Ah-1ahB344.文法的喬姆斯基體系文法的喬姆斯基體系故在故在G中中以下推導(dǎo)過程成立：以下推導(dǎo)過程成立：A

25、 Ga a1 1A A1 1 Ga a1 1a a2 2A A2 2 Ga a1 1a a22a ah-1h-1A Ah-1h-1 Ga a1 1a a22a ah-1h-1a ah hB B因為因為A Gx x1 1B B Gkx x1 1x x2 2，即即B B Gkx x2 2由歸納假設(shè)由歸納假設(shè)n=kn=k時時結(jié)論成立，所以存在結(jié)論成立，所以存在m m，使得，使得B B Gmx x2,2,所以下列推所以下列推導(dǎo)成立：導(dǎo)成立： Ga a1 1a a22a ah-1h-1a ah hx x2 2 Gx x1 1x x2 2即當(dāng)即當(dāng)n=k+1n=k+1時，時， A Gn x A G+ + x成立成立354.文法的喬姆斯基體系文法的喬姆斯基體系(2)證明證明A G+ x AG + x設(shè)設(shè)A Gn x （即從（即從A出發(fā)，經(jīng)過出發(fā)，經(jīng)過n步得到步得到x）當(dāng)當(dāng)n=1時，必存在時，必存在Ax P P 所以所以x x是終極符號是終極符號根據(jù)根據(jù)PP中產(chǎn)生式構(gòu)造的方法，必有中產(chǎn)生式構(gòu)造的方法，必有Ax P P存在，即存在，即AG x成立。成立。假設(shè)假設(shè)nk時時A Gk-1x AG +x成立，往證成立，往證n=k（k 2）時時A Gkx AG +x也成立。也成立。364.文法的喬姆斯基體系文法的喬姆斯基體系根據(jù)根據(jù)G的定義，對于第一種類型的產(chǎn)生式，以下推導(dǎo)的定