1、第2章 文法 對任何語言L，有一個字母表，使得L* 。 L的具體組成結構是什么樣的？一個給定的字符串是否為一個給定語言的句子?如果不是，它在結構的什么地方出了錯？進一步地，這個錯誤是什么樣的錯？如何更正？。這些問題對有窮語言來說，比較容易解決。這些問題對無窮語言來說，不太容易解決。語言的有窮描述。2022/10/11第2章 文法 主要內容 文法的直觀意義與形式定義，推導、文法產生的語言、句子、句型；喬姆斯基體系，左線性文法、右線性文法，文法的推導與歸約；空語句。重點 文法、推導、歸約、模型的等價性證明。難點 形式化的概念，文法的構造。2022/10/122.1 啟示 文法的概念最早是由語言學家

2、們在研究自然語言理解中完成形式化。 歸納如下句子的描述： 哈爾濱是美麗的城市。 北京是祖國的首都。 集合是數學的基礎。 形式語言是很抽象的。 教育走在社會發展的前面。 中國進入WTO。 2022/10/132.1 啟示 6個句子的主體結構 =哈爾濱，北京，集合，形式語言，教育，中國=是美麗的城市，是祖國的首都，是數學的基礎，是很抽象的，走在社會發展的前面，進入WTO =。 2022/10/142.1 啟示 可以是 或者 。=北京、哈爾濱、形式語言、中國、教育、集合、WTO、美麗的城市、祖國的首都、數學的基礎、社會發展的前面。 =是、走在、進入。=很抽象的。把取名為。 2022/10/152.1

3、 啟示 2022/10/162.1 啟示表示成形式是2022/10/172.1 啟示走在進入很抽象的北京哈爾濱形式語言2022/10/182.1 啟示中國教育集合 WTO美麗的城市祖國的首都數學的基礎社會發展的前面。2022/10/192.1 啟示表示一個語言，需要4種東西 形如的 “符號” 它們表示相應語言結構中某個位置上可以出現的一些內容。每個“符號”對應的是一個集合，在該語言的一個具體句子中，句子的這個位置上能且僅能出現相應集合中的某個元素。所以，這種“符號”代表的是一個語法范疇。 所有的“規則”，都是為了說明的結構而存在，相當于說，定義的就是。2022/10/1102.1 啟示 形如北

4、京的“符號” 它們是所定義語言的合法句子中將出現的“符號”。僅僅表示自身，稱為終極符號。 所有的“規則”都呈的形式 在產生語言的句子中被使用，稱這些“規則”為產生式。 2022/10/1112.2 形式定義 文法(grammar) G=(V，T，P，S) V為變量(variable)的非空有窮集。AV，A叫做一個語法變量(syntactic Variable)，簡稱為變量，也可叫做非終極符號(nonterminal)。它表示一個語法范疇(syntactic Category)。所以，本文中有時候又稱之為語法范疇。 2022/10/1122.2 形式定義T為終極符(terminal)的非空有窮集

5、。aT，a叫做終極符。由于V中變量表示語法范疇，T中的字符是語言的句子中出現的字符，所以，有VT=。 SSV，為文法G的開始符號(start symbol)。 2022/10/1132.2 形式定義 P為產生式(production)的非空有窮集合。P中的元素均具有形式，被稱為產生式，讀作：定義為。其中(VT)+，且中至少有V中元素的一個出現。(VT)*。稱為產生式的左部，稱為產生式的右部。產生式又叫做定義式或者語法規則。 2022/10/1142.2 形式定義 例 2-1 以下四元組都是文法。 (A，0，1，A01，A0A1，A1A0，A)。 (A，0，1，A0，A0A，A)。 (A，B，0

6、，1，A01，A0A1，A1A0，BAB，B0，A)。 (A，B，0，1，A0，A1，A0A，A1A ，A)。2022/10/1152.2 形式定義 (S，A，B，C，D,a，b，c，d,#，SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d，S)。 (S,a，b，S00S，S11S，S00，S11，S)。 2022/10/1162.2 形式定義 約定 對一組有相同左部的產生式1，2 ， ，n可以簡單地記為：1|2|n讀作：定義為1，或者2，或者n。并且稱它們為產生式。1，2，n稱為候選式(candidate)。 2022/10/1

7、172.2 形式定義 使用符號英文字母表較為前面的大寫字母，如A，B，C，表示語法變量；英文字母表較為前面的小寫字母，如a，b，c，表示終極符號；英文字母表較為后面的大寫字母，如X，Y，Z，表示該符號是語法變量或者終極符號；英文字母表較為后面的小寫字母，如x，y，z，表示由終極符號組成的行；希臘字母，表示由語法變量和終極符號組成的行 2022/10/1182.2 形式定義 例 2-3 四元組是否滿足文法的要求。 (A，B，C，E，a，b，c，SABC|abc，De|a，FBc，AA，E abc|，S) 4種修改 (1) (A，B，C，E，S，D，F，a，b，c，e，SABC|abc，De|a，

8、FBc，AA，E abc|，S)。 (2) (A，B，C，E，S ，a，b，c，SABC|abc，AA，E abc|，S)。(3) (A，B，C，E，a，b，c， AA，E abc|，A)。 (4) (A，B，C，E，a，b，c， AA，E abc|，E)。2022/10/1192.2 形式定義推導(derivation) 設G=(V，T，P，S)是一個文法，如果P，(VT)*，則稱在G中直接推導出。 G 讀作：在文法G中直接推導出。“直接推導”可以簡稱為推導(derivation)，也稱推導為派生。 2022/10/1202.2 形式定義歸約(reduction) G 稱在文法G中直接歸約成

9、。在不特別強調歸約的直接性時，“直接歸約”可以簡稱為歸約。 2022/10/1212.2 形式定義1 推導與歸約表達的意思的異同。2推導與歸約和產生式不一樣。所以，G和所表達的意思不一樣。3 推導與歸約是一一對應的。4 推導與歸約的作用。2022/10/1222.2 形式定義G、G+、G*當成(VT)*上的二元關系。 (1)Gn ：表示在G中經過n步推導出；在G中經過n步歸約成。即，存在1，2，n-1(VT)*使得G 1，1G 2，n-1G 。 (2)當n=0時，有=。即G0 。 (3)G+ ：表示在G中經過至少1步推導出；在G中經過至少1步歸約成。 2022/10/1232.2 形式定義(4

10、)G* ：表示在G中經過若干步推導 出；在G中經過若干步歸約成。 分別用、+、*、n代替G、G+、G*、Gn 。2022/10/1242.2 形式定義例 2-4 設G=(A，a，Aa|aA，A)A aA使用產生式AaA aaA使用產生式AaA aaaA使用產生式AaA aaaaA使用產生式AaAaaA使用產生式AaAaaa使用產生式Aa2022/10/1252.2 形式定義A aA使用產生式AaAaaA使用產生式AaAaaaA使用產生式AaAaaaaA使用產生式AaAaaA使用產生式AaAaaaA使用產生式AaA2022/10/1262.2 形式定義AAaaAAA AAaaAaAA使用產生式A

11、aA AaAaaAaAA使用產生式AaA AaAaaAaaA使用產生式Aa aaAaaAaaA使用產生式Aa aaAaaAaaa使用產生式Aa aaaAaaAaaa使用產生式AaA aaaaaaAaaa使用產生式Aa aaaaaaaaaa使用產生式Aa 2022/10/1272.2 形式定義例 2-5 設G=(S，A，B，0，1，SA|AB，A0|0A，B1|11，S) 對于n1，A n 0n首先連續n-1次使用產生式；A0A， 最后使用產生式A0；A n 0nA連續n次使用產生式A0A； B 1使用產生式B1；B 11使用產生式B11。 2022/10/1282.2 形式定義語法范疇A代表的

12、集合L(A)=0，00，000，0000，=0n|n1；語法范疇B代表的集合L(B)=1，11語法范疇S代表的集合L(S)=L(A)L(A)L(B) =0，00，000，0000，0，00，000，0000，1，11 =0，00，000，0000，01，001，0001，00001，011，0011，00011，000011， 2022/10/1292.2 形式定義例2-6 設G=(A，0，1，A01，A0A1，A)，A n 0nA1nn0 0nA1n 0n+1A1n+1n00nA1n 0n+11n+1n00nA1n i 0n+iA1n+in0，i00nA1n i 0n+i1n+In0，i00

13、nA1n * 0mA1mn0，mn0nA1n + 0m1mn0，mn+10nA1n + 0mA1mn0，mn+10nA1n + 0m1mn0，mn+1 2022/10/1302.2 形式定義幾點結論對任意的x+，我們要使語法范疇D代表的集合為xn|n0，可用產生式組D|xD來實現。 對任意的x，y+，我們要使語法范疇D代表的集合為xnyn|n1，可用產生式組Dxy|xDy來實現。 對任意的x，y+，我們要使語法范疇D代表的集合為xnyn|n0，可用產生式組D|xDy來實現。 2022/10/1312.2 形式定義語言(language) L(G)=w | wT*且S * w 句子(senten

14、ce) wL(G)，w稱為G產生的一個句子。句型(sentential form) G=(V，T，P，S)，對于(VT)*，如果S * ，則稱是G產生的一個句型。2022/10/1322.2 形式定義句子w是從S開始，在G中可以推導出來的終極符號行，它不含語法變量。 句型是從S開始，在G中可以推導出來的符號行，它可能含有語法變量。 例 2-7 給定文法G=(S，A，B，C，D,a，b，c，d,#，SABCD|abc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d，S) 2022/10/1332.2 形式定義S ABCD 使用產生式SABCDaaABC

15、D 使用產生式AaaAaaaaABCD使用產生式AaaAaaaaaabbBCD 使用產生式ABaabbBaaaaaabbbbccCD使用產生式BCbbccCaaaaaabbbbccccCD使用產生式cCcccCaaaaaabbbbcccc#d使用產生式CD#d 2022/10/1342.2 形式定義S ABCD 使用產生式SABCDAbbccCD使用產生式BCbbccCaaAbbccCD使用產生式AaaAaaAbbccccd#使用產生式CDccd#aaaaAbbccccd# 使用產生式AaaAaaaaaaAbbccccd#使用產生式AaaAaaaaaaaaAbbccccd#使用產生式AaaA2

16、022/10/1352.2 形式定義例 2-8 構造產生標識符的文法 G=(，0，1，9，A，B，C，Z，a，b，c，z，P, )P= | ，| ，A|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 ，a|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 ，0|1|2|3|4|5|6|7|8|9 2022/10/1362.2 形式定義G=(，0，1，2，9，A，B，C，Z，a，b，c，z，P, )P= ，A|B|C|D|E|F|G|H|I|J|K|L|M|N O|P|Q|R|S|T|U|V|

17、W|X|Y|Z ，a|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 ，2022/10/1372.2 形式定義|0|1|2|3|4|5, 6|7|8|9 ，A|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|a|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 2022/10/1382.2 形式定義 3 32323 n23 n238n238n23 d8n23d8n23 id8n232022/10/1392.2 形式定義標識

18、符 i id id8 id8n id8n2 id823 id8n232022/10/1402.2 形式定義使用符號使文法更簡潔G=(,b，a，d,b|a|b|a|d, ) G=(L，b，a，d，Lb|a|Lb|La|Ld, L) G=(L，H，T， b，a，d ，LHT，Hb|a，T|bT|aT|dT, L) 2022/10/1412.3 文法的構造 例2-9 構造文法G，使L(G)=0，1，00，11 將文法的開始符號定義為這4個句子。 G1=(S，0，1，S0，S1，S00，S11，S) 先用變量A表示0，用變量B表示1。 G2=(S，A，B，0，1，SA，SB，SAA，SBB，A0，B1

19、，S) 基于G2，考慮“規范性”問題。 G3=(S，A，B，0，1，S0，S1，S0A，S1B，A0，B1，S) 2022/10/1422.3 文法的構造可以在V、T中增加一些元素，以獲得“不同的”文法。 G4=(S，A，B，C，0，1，2，SA，SB，SAA，SBB，A0，B1，S) G5=(S，A，B，C，0，1，2，SA，SB，SAA，SBB，A0，B1，CACS21，C11，C2，S) L(G1)= L(G2)= L(G3)= L(G4)= L(G5) 2022/10/1432.3 文法的構造 等價(equivalence)設有兩個文法G1和G2，如果L(G1)= L(G2)，則稱G1

20、與G2等價。 約定對一個文法，只列出該文法的所有產生式，且所列第一個產生式的左部是該文法的開始符號。 2022/10/1442.3 文法的構造 G1：S0|1|00|11G2：SA|B|AA|BB，A0，B1G3：S0|1|0A|1B，A0，B1G4：SA|B|AA|BB，A0，B1G5：SA|B|BB，A0，B1，CACS21，C11，C22022/10/1452.3 文法的構造 例 2-10L=0n|n1 G6：S0|0S L=0n|n0 G7：S|0SL=02n13n|n0 G8：S|00S1112022/10/1462.3 文法的構造 例2-11 構造文法G9，使L(G9)=w|wa，

21、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生成 An。 不可以用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可以產生任意多個a。 2022/10/1472.3 文法的構造 例2-12 構造文法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)

22、。2022/10/1482.3 文法的構造 wwT|w0，1，2，3+的句子的特點 設w=a1a2an，從而有wT= ana2 a1，故w wT= 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)任何其他的串。 2022/10/1492.3 文法的構造 根據遞歸定義中的第一條，有如下產生式組：S00 | 11 | 22 | 33再根據遞歸定義第二條，又可得到如下產生式組：S0S0 | 1S1 | 2S2 | 3S3從而，G10：S00

23、| 11 | 22 | 33 | 0S0 | 1S1 | 2S2 | 3S3 2022/10/1502.3 文法的構造 例2-13 構造文法G12，使L(G12)=w|w是我們習慣的十進制有理數。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 | 9M2022/10/1512.3 文法的構造 例2-14 構造產生算術表達式的文法： 基礎：常數是算術表達式，變量是算術表達式； 歸納：如果E1、E2是表達式

24、，則 +E1、-E1、E1+E2、 E1-E2 、E1*E2 、E1/E2、E1*E2、Fun(E1)是算術表達式。其中Fun為函數名。 只有滿足(1)和(2)的才是算術表達式。 G13：Eid|c|+E|-E|E+E|E-E|E*E|E/E|E*E|Fun(E) 2022/10/152 2.3 文法的構造例2-15 構造產生語言anbncn|n1的文法。 文法G=(S1，a，b，S1ab | aS1b，S1)產生的語言anbn | n1形式上看起來與語言anbncn | n1比較接近。G=(S2，c，S2c | cS2，S2)產生的語言是cn|n1。anbncn | n1anbn | n1c

25、n | n1 2022/10/1532.3 文法的構造文法SS1S2S1ab | aS1bS2c | cS2 不能產生語言anbncn | n1 而是產生語言 anbn | n1cn | n1 2022/10/1542.3 文法的構造文法G：Sabc | aSbc 產生的語言為：an(bc)n | n1 焦點：交換b和c的位置。2022/10/1552.3 文法的構造G14：SaBC | aSBC， CBBC aBab bBbb bCbc cCccG14：Sabc|aSBc， bBbb cBBc 2022/10/156文法的喬姆斯基體系 文法G=(V，T，P，S) G叫做0型文法(type 0

26、 grammar)，也叫做短語結構文法(phrase structure grammar, PSG)。L(G)叫做0型語言。也可以叫做短語結構語言(PSL)、遞歸可枚舉集(recursively enumerable ，r.e. )。 2022/10/157文法的喬姆斯基體系 G是0型文法。如果對于P，均有|成立，則稱G為1型文法(type 1 grammar)，或上下文有關文法(context sensitive grammar,CSG)。L(G)叫做1型語言(type 1 language)或者上下文有關語言(context sensitive language ,CSL)。2022/10

27、/158文法的喬姆斯基體系 G是1型文法如果對于P，均有|，并且V成立，則稱G為2型文法(type 2 grammar)，或上下文無關文法(context free grammar,CFG)。L(G)叫做2型語言(type 2 language)或者上下文無關語言(context free language ,CFL)。 2022/10/159文法的喬姆斯基體系 G是2型文法如果對于P，均具有形式 Aw AwB其中A，BV，wT+。則稱G為3型文法(type 3 grammar)，也可稱為正則文法(regular grammar ,RG)或者正規文法。L(G)叫做3型語言(type 3 lan

28、guage)，也可稱為正則語言或者正規語言(regular language ,RL)。 2022/10/160文法的喬姆斯基體系 如果一個文法G是RG，則它也是CFG、CSG和短語結構文法。反之不一定成立。 如果一個文法G是CFG，則它也是CSG和短語結構文法。反之不一定成立。 如果一個文法G是CSG，則它也是短語結構文法。反之不一定成立。相應地： RL也是CFL、CSL和短語結構語言。反之不一定成立。2022/10/161文法的喬姆斯基體系 CFL也是CSL和短語結構語言。反之不一定成立。 CSL也是短語結構語言。反之不一定成立 當文法G是CFG時，L(G)卻可以是RL。 當文法G是CSG

29、時，L(G)可以是RL、CSL。 當文法G是短語結構文法時，L(G)可以是RL、CSL和CSL。 2022/10/162文法的喬姆斯基體系 定理 2-1 L是RL的充要條件是存在一個文法，該文法產生語言L，并且它的產生式要么是形如：Aa的產生式，要么是形如AaB的產生式。其中A、B為語法變量，a為終極符號。 證明 ：充分性：設有G，L(G)=L，且G的產生式的形式滿足定理要求。這種文法就是RG。所以，G產生的語言就是RL，故L是RL。 2022/10/163文法的喬姆斯基體系必要性 構造：用產生式組：Aa1A1A1a2A2An-1an代替產生式A a1a2an 2022/10/164文法的喬姆

30、斯基體系用產生式組Aa1A1A1a2A2An-1anB代替產生式A a1a2an B2022/10/165文法的喬姆斯基體系證明L(G)=L(G) 。 施歸納于推導的步數，證明一個更一般的結論：對于AV，A G+ xA G+ x。因為SV，所以結論自然對S成立。 2022/10/166文法的喬姆斯基體系幾點注意事項 我們是按照RG的一般定義來構造一個與之等價的文法的，這與讀者以前熟悉的根據一個具體的對象構造另一個對象是不同的。在這里，可以使用的是非常一般的條件一個一般模型。這也是這類問題的證明所要求的。而且在本書的后面，將會有更多這樣的情況。2022/10/167文法的喬姆斯基體系 為了證明一

31、個特殊的結論，可以通過證明一個更為一般的結論來完成。這從表面上好像是增加了我們要證明的內容，但實際上它會使我們能夠更好地使用歸納假設，以便順利地獲得我們所需要的結論。2022/10/168文法的喬姆斯基體系 施歸納于推導的步數是證明本書中不少問題的較為有效的途徑。有時我們還會對字符串的長度施歸納。本證明的主要部分含兩個方面，首先是構造，然后對構造的正確性進行證明。這種等價性證明的思路是非常重要的。2022/10/169文法的喬姆斯基體系線性文法(liner grammar) 設G=(V，T，P，S)，如果對于P，均具有如下形式：AwAwBx其中A，BV，w，xT*，則稱G為線性文法。線性語言(

32、liner language) L(G)叫做線性語言2022/10/170文法的喬姆斯基體系右線性文法(right liner grammar) 設G=(V，T，P，S)，如果對于P，均具有如下形式：AwAwB其中A，BV，w，xT*，則稱G為線性文法。右線性語言(right liner language) L(G)叫做右線性語言。2022/10/171文法的喬姆斯基體系 左線性文法(left liner grammar) 設G=(V，T，P，S)，如果對于P，均具有如下形式：AwABw其中A，BV，w，xT*，則稱G為線性文法。左線性語言(left liner language) L(G)叫

33、做右線性語言。2022/10/172文法的喬姆斯基體系定理2-2 L是一個左線性語言的充要條件是存在文法G，G中的產生式要么是形如：Aa的產生式，要么是形如ABa的產生式，使得L(G)=L。其中A、B為語法變量，a為終極符號。 2022/10/173文法的喬姆斯基體系定理2-3 左線性文法與右線性文法等價。 按照定理2-1的證明經驗，要想證明本定理，需要完成如下工作：對任意右線性文法G，我們能夠構造出對應的左線性文法G，使得L(G)=L(G)；對任意左線性文法G，我們能夠構造出對應的右線性文法G，使得L(G)=L(G)。2022/10/174文法的喬姆斯基體系例 2-17 語言0123456的

34、左線性文法和右線性文法的構造。右線性文法Gr：Sr0ArAr1BrBr2CrCr3DrDr4ErEr5FrFr6 2022/10/175文法的喬姆斯基體系在文法Gr中的推導 Sr0Ar使用產生式Sr0Ar 01Br使用產生式Ar1Br 012Cr使用產生式Br2Cr 0123Dr使用產生式Cr3Dr 01234Er使用產生式Dr4Er 012345Fr使用產生式Er5Fr 0123456使用產生式Fr62022/10/176文法的喬姆斯基體系左線性文法Gl：SlAl6 AlBl5 BlCl4 ClDl3 DlEl2 ElFl1 Fl0 2022/10/177文法的喬姆斯基體系2022/10/1

35、78文法的喬姆斯基體系在文法Gl中的推導 SlAl6使用產生式SlAl6 Bl56使用產生式AlBl5 Cl456使用產生式BlCl4 Dl3456使用產生式ClDl3 El23456 使用產生式DlEl2 Fl1234456使用產生式ElFl1 0123456使用產生式Fl0 2022/10/179文法的喬姆斯基體系被歸約成文法Gl的開始符號S 0123456 Fl1234456使用產生式Fl0 El23456使用產生式ElFl1 Dl3456使用產生式DlEl2 Cl456使用產生式ClDl3 Bl56使用產生式BlCl4 Al6使用產生式AlBl5 Sl使用產生式SlAl6 2022/1

36、0/180文法的喬姆斯基體系2022/10/181文法的喬姆斯基體系定理 2-4 左線性文法的產生式與右線性文法的產生式混用所得到的文法不是RG。證明：設有文法G15：S0AAS1|1 不難看出，L(G15)=0n1n|n1。我們構造不出RG G，使得L(G)= L(G15)=0n1n|n1。因為L(G15)=0n1n|n1不是RL。所以，G15不是RG。有關該語言不是RL的證明我們將留到研究RL的性質時去完成。 2022/10/1822.5 空語句 形如A的產生式叫做空產生式，也可叫做產生式。 在RG、CFG、CSG中，都不能含有空產生式。所以，任何CSL中都不含有空語句。從而CFL和RL中

37、都不能含空語句。 空語句在一個語言中的存在并不影響該語言的有窮描述的存在性，甚至除了為生成空語句外，空產生式可以不被用于語言中其他任何句子的推導中。 2022/10/1832.5 空語句 允許CSL、CFL、RL包含空語句后，還會給我們進行問題的處理提供一些方便。 允許在RG、CFG、CSG中含有空產生式允許CSL、CFL、RL包含空語句。 2022/10/1842.5 空語句 定理2-5 設G=(V，T，P，S)為一文法，則存在與G同類型的文法G=(V，T，P，S)，使得L(G)=L(G)，但G的開始符號S不出現在G的任何產生式的右部。證明：構造當文法G=(V，T，P，S)的開始符號S不出現

38、在P中的任何產生式的右部時，G就是所求 G=(VS，T，P，S) P=PS|SP 2022/10/1852.5 空語句 證明L(G) L(G) 對任意的xL(G)，由文法產生的語言的定義知，在G中存在如下推導： S使用產生式S *x使用P中的除S以外的其他產生式。 在推導*x中使用的產生式都是P中的產生式。因此，推導*x在G中仍然成立。 2022/10/1862.5 空語句 由P的定義知，必有SP 所以， S使用P中的產生式S *x使用P中的產生式 故， L(G)L(G) 2022/10/1872.5 空語句 設G中存在如下推導： S使用P中的產生式S *x使用P中的產生式由P=PS|SP ，

39、知道G中， S使用產生式S *x使用P所包含的P中的其他產生式。 故，L(G)L(G)。 2022/10/1882.5 空語句 設G=(V，T，P，S)是一個文法，如果S不出現在G的任何產生式的右部，則： 如果G是CSG，則仍然稱G=(V，T，PS，S)為CSG；G產生的語言仍然稱為CSL。 如果G是CFG，則仍然稱G=(V，T，PS，S)為CFG；G產生的語言仍然稱為CFL。 如果G是RG，則仍然稱G=(V，T，PS，S)為RG。G產生的語言仍然稱為RL。2022/10/1892.5 空語句 定理2-6 下列命題成立： 如果L是CSL，則L仍然是CSL。 如果L是CFL，則L仍然是CFL。 如果L是RL