形式語言與自動機文法的一般理論

1、1形式語言與自動機（Formal Languages and Automata） 第二章 文法的一般理論南京航空航天大學(xué)南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)學(xué)院 胡胡 軍軍2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍2o2.1 問題的提出 o2.2 形式文法與形式語言 o2.3 文法的喬姆斯基分類2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍32.1 問題的提出o 任何有意義的語言都不是任意字符串的集合，而是符合某些規(guī)則要求的字符串集合符合某些規(guī)則要求的字符串集合.n 自然語言(英語，語法)；n 程序設(shè)計語言(C語言，文法)； o 文法(Grammar

2、): 用有限個規(guī)則描述無窮有限個規(guī)則描述無窮多字符串的集合n 自然語言描述(如：英語語法)；n 嚴(yán)格的形式規(guī)則描述（如：C語言文法、Pascal 語言文法）- 形式文法，形式文法， 形式語言形式語言2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍4BNF(Backus-Naur Form) o例2.1 在類PasCal語言中，是用下述一組規(guī)則一組規(guī)則定義的：:= := IFTHENElSE:= WHILEDO:=BEGINEND:= ；: :=:=: :=: := | = : :=|（）: := +|-|*|/: := 0|1|2|3|4|5|6|7|8|9:= a|b|c|d|e|

3、f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍5問題的提出o 例2.2 根據(jù)例2.1中的各規(guī)則，下述的字符串 WHILE x5 DO x := (x+2) 是一個合法的語句;因為：n整個符合的定義結(jié)構(gòu)；nx5是的一種；nx := （x+1）是的一種（從而也是的一種）；2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍6語法樹(分析樹，Parser Tree)2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍7問題的提出o 例2.3 用下述語法規(guī)則定義英語中的句子。 the a appl

4、e cat man eats sings runsthe apple runs 語法語法/語義語義ArticleArticle2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍82.2 形式文法與形式語言 o定義2. 1 一個文法文法G是一個四元組 G = ( V, T, P, S )，其中：nV：是變元變元（Variable，Nonterminal）的有限集。nT：是終結(jié)符終結(jié)符（Terminal）的有限集。nP：是產(chǎn)生式產(chǎn)生式（Production）的有限集，其中每個產(chǎn)生式都是的形式，其中(VT)+，且其中至少有一個V中的符號，(VT)*。稱為產(chǎn)生式的左部產(chǎn)生式的左部，稱為產(chǎn)生式的

5、右部。產(chǎn)生式的右部。nSV，稱為文法G的開始符號開始符號。(S很重要，決定這組規(guī)則最終要定義什么，考慮例2.3中的和)n例2.4: nG1 = (A, B, 0,1,A0B, B1B, B0, A)。nG2 =( A,B,C,a,b,C,AaBC, Bb, CCC, C, A)。nG3=( L,M,N, 0,1,2, M0LN, L1, 0L2, LN12，N0，M)。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍9文法表示方法的約定o 凡有關(guān)文法的例子，都遵循下述的約定：n大寫拉丁字母A,B,C,D,E和S等等表示變元變元，除非另做說明，S表示開始符號。n小寫拉丁字母a,b,c,

6、d,e,數(shù)字等等表示終結(jié)符終結(jié)符。n小寫拉丁字母u, v, w, x, y, z等等表示終結(jié)符串終結(jié)符串。n小寫希臘字母，等等表示變元和終結(jié)符共同組成變元和終結(jié)符共同組成的串的串。o 另外還約定，同一個文法中如果有若干個左部相同而右部不同的產(chǎn)生式，如：1，2，no則可以縮寫為：1|2|n 在上述約定下，寫一個文法時，只寫出它的產(chǎn)生式集合就可以了.2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍10字符串的推導(dǎo) 與 歸約o 定義2.2 給出文法 G = ( V, T, P, S )，我們定義兩個字符串之間的一個關(guān)系關(guān)系“ ”：若 = 123, =13, 并且2是P中的一個產(chǎn)生式，則有

7、，此時稱由直接推導(dǎo)直接推導(dǎo)出。根據(jù)第一章關(guān)于集合上關(guān)系的閉包的定義，我們也可將 擴充為 ，將 稱為由推導(dǎo)推導(dǎo)出。o 若有S ，則稱為句型句型，當(dāng)，則稱為句子句子。o 對應(yīng)于推導(dǎo)，還有一個重要的概念，稱為“歸約歸約”。其定義是：如果 是由到的推導(dǎo)，則反過來稱歸約到，記作 。GGGGGGGG2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍11字符串的推導(dǎo) 與 規(guī)約o例2.7 對于例2.6中給出的文法G，我們有： S 0A1 00A11 000A111 000111o第一步直接推導(dǎo)用的是第（1）個產(chǎn)生式，第二步直接推導(dǎo)用的是第（2）個產(chǎn)生式，第三步直接推導(dǎo)還是用第（2）個產(chǎn)生式，最后一步直

8、接推導(dǎo)用的是第（3）個產(chǎn)生式?？偲饋砦覀円部梢詫憺镾 000111。在這個推導(dǎo)中，0A1，00A11，000A111 , 000111都是句型，而000111又是句子。o在今后寫推導(dǎo)式子的時候，若所指的文法是明確無誤的，則可將記號 或 中的G省略，只寫 或 即可。另外，如果經(jīng)過i步的直接推導(dǎo)到，就可寫 。GGGGGGGi2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍12形式文法與形式語言o 定義2.3 給出文法 G=(V,T,P,S)，它所產(chǎn)生的語言記作(G)，由下述集合定義： L(G)=|S ，并且* 。換句話說，文法G產(chǎn)生的語言(G)，就是由由G中開始中開始符號符號S推導(dǎo)出來的

9、全體終結(jié)符號串所構(gòu)成的集合推導(dǎo)出來的全體終結(jié)符號串所構(gòu)成的集合，也就是句子的集合句子的集合。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍13文法 語言o例2.8 給出文法G,它有兩個產(chǎn)生式： SaSbSab則該文法產(chǎn)生的語言(G)=an bn n1 。o這是根據(jù)(G)的定義，考慮從S的推導(dǎo)，若先用G中第二個產(chǎn)生式，則S ab，就不能再往下推導(dǎo)了，此時相當(dāng)于語言中1的情況。若從S出發(fā)，先用第一個產(chǎn)生式-1次，即S aSb aaSbb an-1S bn-1，最后再使用第二個產(chǎn)生式一次，得到S ab，這個推導(dǎo)對于任何1都是對的。再加上=1的情況，即可得到L(G)an bn n1 。20

10、22年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍14文法語言o例2.9給出文法G，它的產(chǎn)生式是：SaB bAAa bAA aSBb aBB bS(G)是由相等個數(shù)a和b組成的（次序不限）所有串的集合，加以證明。為了證明最終的結(jié)論，要證明以下三個互相關(guān)聯(lián)的命題。oS ，當(dāng)且僅當(dāng)中包含相等個數(shù)的a和b。oA ，當(dāng)且僅當(dāng)中a的個數(shù)比b的個數(shù)多1。B ，當(dāng)且僅當(dāng)中b的個數(shù)比a的個數(shù)多1。*2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍15文法語言下面我們用關(guān)于關(guān)于w長度的歸納法長度的歸納法(多重歸納法多重歸納法)來證明上述三個命題。歸納基礎(chǔ)歸納基礎(chǔ) w 1。命題（2），（3）顯然是對

11、的，因為只能有A a，B b，用其他產(chǎn)生式時都將推導(dǎo)出長度大于1的串。對于命題（1），因為在 w 1這個大前提下，一方面不可能有S w，另一方面中也不可能包含相等個數(shù)的a和b，即“當(dāng)且僅當(dāng)”的兩個方面都是假的，故命題（1）自然成立。歸納步驟歸納步驟假設(shè)對于所有長度不超過k-1的串，命題（1），（2），（3）成立，現(xiàn)在要證當(dāng)wk時（k2），命題（1），（2），（3）也成立。*2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍16文法語言o先證命題（先證命題（1）。o如果S ，那么推導(dǎo)的第一步必然是S aB或S bA。對于第一種情形，必然有aw1，且B w1，因為 w1 k1，則根據(jù)歸納法

12、假設(shè)，它包含b的個數(shù)比a的個數(shù)多1（命題（2），因此包含a的個數(shù)與b的個數(shù)相等。o對于S bA的情形，證明完全類似。o反之，如果 w k，且w包含相等個數(shù)的a和b，要證S w?？紤]w的第一個符號只有a或b兩種情況，若是a，則waw1，且 w1 k1。由于w1中包含b的個數(shù)比a的個數(shù)多1，根據(jù)歸納法假設(shè)，必有B w1（命題（3）。此時使S的第一次直接推導(dǎo)為S aB，然后將B推導(dǎo)到1，最后得到S aw1w。o對于w以b開始的情況，可以完全類似地證明。o考慮再證明命題（2）和（3）。*2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍17語言文法o例2.10 給出語言 a 1，找出產(chǎn)生它的文

13、法。oa，aa，aaa，它是一個無限集。因此必須先產(chǎn)生出一個a來，我們首先用產(chǎn)生式Sa來實現(xiàn)。因為是無限集，必須用遞歸的方法，以一個a為基礎(chǔ)，不斷地添加一個a。即再用一個產(chǎn)生式SaS，與第一個產(chǎn)生式合起來，整個文法就是：SaSaSo當(dāng)然，產(chǎn)生的文法不是唯一的，我們也可以用以下兩個產(chǎn)生式SaSSao還可以用文法SaSS2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍18語言文法o 例2.11 構(gòu)造一個文法，使其能產(chǎn)生語言a，b* 。nw是由a和b以任意次序組成的串（包括空串），w是w的逆轉(zhuǎn)，ww是由偶數(shù)個a，b組成且由中心開始左右對稱的串，如abba，baaaab，aabaabaa等等

14、。o 例2.12構(gòu)造一個文法，使其能產(chǎn)生語言anbncn1。 （不太容易）2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍19文法等價 o定義2.4對于兩個不同的文法G1 (V1，T1，P1，S1），G2(V2，T2，P2，S2)，如果如果(G1)(G2)，則稱文法，則稱文法G1與與G2等價等價。o同一個語言可以由不同的文法產(chǎn)生同一個語言可以由不同的文法產(chǎn)生。在例2.2.7中已經(jīng)看到，一個很簡單的語言an|n1就可由三個不同的文法產(chǎn)生。o文法是用四元組定義的，在兩個四元組的各對應(yīng)部分中，只要有一點點不同，就應(yīng)當(dāng)看作是不同的文法。如在一個已有的文法上，隨意加上一些變元，一些終結(jié)符，或一

15、些不影響S推導(dǎo)結(jié)果的產(chǎn)生式等等，都會變成新的文法。在這個意義下，任何一個語言都可在這個意義下，任何一個語言都可以有無窮多個文法產(chǎn)生它以有無窮多個文法產(chǎn)生它。 2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍202.3 文法的喬姆斯基分類o 定義 2.5 對于文法G（V，T，P，S）按以下方法分為四類：n 若中的產(chǎn)生式，不加另外的限制，則G稱為0型文法型文法，或短語結(jié)短語結(jié)構(gòu)文法構(gòu)文法（PSG）。 n 若中每個產(chǎn)生式都滿足條件| |，則G稱為1型文法型文法，或上下文有關(guān)文法上下文有關(guān)文法（ CSG ） 。n 若中每個產(chǎn)生式都具有如下形式： A，(VT)*，AV， 則稱G為2型文法型文法

16、，或上下文無關(guān)文法上下文無關(guān)文法（ CFG ）。n 若中每個產(chǎn)生式都具有如下形式：n Aa或AaB，aT，A，BV ， 則稱G為3型文法型文法，或正則文法正則文法（ RG ）。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍21文法的喬姆斯基分類o 定義2.6 n由短語結(jié)構(gòu)文法產(chǎn)生的語言，稱為短語結(jié)構(gòu)語言短語結(jié)構(gòu)語言，簡記為PSL。n由上下文有關(guān)文法產(chǎn)生的語言，稱為上下文有關(guān)語言上下文有關(guān)語言，簡記為CSL。n由上下文無關(guān)文法產(chǎn)生的語言，稱為上下文無關(guān)語言上下文無關(guān)語言，簡記為CFL。n由正則文法產(chǎn)生的語言，稱為正則語言正則語言，簡記為RL。2022年1月25日星期二南京航空航天大學(xué)

17、計算機學(xué)院 胡軍222022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍23右線性文法o定義2.9 對于文法G =(V,T,P,S),如果P中產(chǎn)生式都呈以下形式:AwAwB這里A,BV, wT* ,則文法G稱為右線性文法右線性文法。類似地，如果P中產(chǎn)生式都呈AwABw形式，這里A,BV, wT* ,則文法G稱為左線性文法左線性文法。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍24右線性文法o定理定理2.2 任何由右線性文法產(chǎn)生的語言都能被正則文法產(chǎn)生。任何由右線性文法產(chǎn)生的語言都能被正則文法產(chǎn)生。o證明 設(shè)L是一個右線性文法G產(chǎn)生的語言，G =(V,T,P,S)。現(xiàn)在由G構(gòu)

18、造正則文法G= (V,T , P,S)，其中P的構(gòu)造為: 對于P中形如Aw的產(chǎn)生式,若w=a(aT)或w=,則已符合正則文法的要求，將它們直接放入P中。對于w=a1a2an(n2),則引入新變元A1,A2,An-1 ,并將以下一組產(chǎn)生式Aa1A1A1a2A2 （*）An-1an加入P中。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍25右線性文法o類似地，對于P中形如AwB的產(chǎn)生式，若 w 2，則將它們直接放入P中。對于w=a1a2an(n2)， 則引入新變元B1,B2,Bn-1 ，并將以下一組產(chǎn)生式 Aa1B1 B1a2B2 （*） Bn-1anB加入P中。oV中的變元就是出現(xiàn)在

19、P中的全部變元。因為G中產(chǎn)生式的個數(shù)是有限的，所以新引入的變元的個數(shù)也是有限的，不管新老變元有多少個，我們可以假設(shè)它們的名字全不相同。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍26右線性文法o下面來證明G與G等價( L(G) L(G) and L(G) L(G) ?)o一方面，設(shè)有S x（xT*）。如果在推導(dǎo)過程中沒有使用Aa1a2an(n2)和Aa1a2anB(n2)形式的產(chǎn)生式，則自然也有S x。如果在推導(dǎo)過程中每使用一次產(chǎn)生式Aa1a2an(n2)，就連續(xù)使用P中以下一組產(chǎn)生式 Aa1A1 A1a2A2 An-1an來替代。G*G2022年1月25日星期二南京航空航天大學(xué)

20、計算機學(xué)院 胡軍27右線性文法如果在推導(dǎo)過程中每使用一次產(chǎn)生式Aa1a2anB(n2)，就連續(xù)使用P中以下一組產(chǎn)生式 Aa1B1 B1a2B2 Bn-1anB來替代。這樣顯然也有S x。因此，L(G) L(G)。*G2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍28右線性文法o另一方面，設(shè)有S x。如果在推導(dǎo)過程中使用了（*）組中的第一個新產(chǎn)生式Aa1A1，因為新引入的變元是成組出現(xiàn)的，而且與其它變元都不相同，則必須連續(xù)使用本組的其余各產(chǎn)生式才行。這樣，這一組連續(xù)推導(dǎo)可以使用G中原來的一個產(chǎn)生式Aa1a2an(n2)用一次推導(dǎo)來代替。如果在G的推導(dǎo)過程中使用了（*）組中的第一個新產(chǎn)

21、生式Aa1B1，則基于同樣的理由，也必須連續(xù)使用本組的其余各產(chǎn)生式才行。那么，這一組連續(xù)推導(dǎo)可以使用G中原來的一個產(chǎn)生式Aa1a2anB(n2)用一次推導(dǎo)來代替，因此也有A x，這就是說L(G) L(G)。最后我們得出L(G)= L(G)。定理證完。o定理定理2.3 任何由左線性文法產(chǎn)生的語言都能被如下的文法任何由左線性文法產(chǎn)生的語言都能被如下的文法G=(V,T,P,S)產(chǎn)生：在產(chǎn)生：在G中的產(chǎn)生式僅為中的產(chǎn)生式僅為Aa和和ABa兩種形式，其兩種形式，其中中aT,A,BV 。*G*G2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍29正則文法o定理定理 2.4 給出正則文法給出正則文

22、法G=(V,T,P,S),且且L(G)=L。則存在另一文法。則存在另一文法G =(V, T, P ,S)，它的產(chǎn)生式僅為，它的產(chǎn)生式僅為Aa和和ABa兩種形式，兩種形式，(其中其中aT,A,BV)，使得，使得L(G)= LR 。o證明 我們由G構(gòu)造G，其出發(fā)點是因為要讓G能產(chǎn)生L的逆轉(zhuǎn)集合LR ，就必須把原來G中產(chǎn)生式的右部也都逆轉(zhuǎn)過來，構(gòu)成G中的產(chǎn)生式。具體來說，P的構(gòu)造是：對于P中形如Aa的產(chǎn)生式(aT A,V)，則將它們?nèi)糠湃隤中。對于P中形如AaB的產(chǎn)生式(aT, A,BV), 則將產(chǎn)生式ABa放入P中。因為G是正則文法,其產(chǎn)生式只有Aa和AaB兩種形式,經(jīng)用上述方法構(gòu)造出來的G ，

23、在形式上已符合定理要求,現(xiàn)在要證L(G)= LR 。2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍30正則文法o一方面,設(shè)x=a1a2anL(G)，要證xR =ana2a1L(G)。o對于n1，在G中有直接推導(dǎo)S x，使用的產(chǎn)生式或為Sa1，或為S。這兩種產(chǎn)生式也在G中，所以，在G中有直接推導(dǎo)S x，而且此時x = xR 。o對于n2，在G中要用一系列直接推導(dǎo)S a1B1 （用產(chǎn)生式Sa1B1）a1a2B2 （用產(chǎn)生式B1a2B2）a1a2an-1Bn-1 （用產(chǎn)生式Bn-2an-1Bn-1）a1a2an-1an （用產(chǎn)生式Bn-1an）或者有 a1a2an-1Bn-1 a1a2an-1anBn （用產(chǎn)生式Bn-1anBn）a1a2an-1an （用產(chǎn)生式Bn）2022年1月25日星期二南京航空航天大學(xué)計算機學(xué)院 胡軍31正則文法o對應(yīng)G中的產(chǎn)生式Sa1B1，G中有SB1a1，對應(yīng)G中的產(chǎn)生式B1a2B2,G中有B1B2a2 , 對應(yīng)G中的產(chǎn)生式Bn-2an-1Bn-1 , G中有Bn-2Bn-1an-1 , 對應(yīng)G中的產(chǎn)生式Bn-1anBn ,G中有Bn-1Bnan 。至于G中的產(chǎn)生式Bn-1an和Bn，G中也有同樣的產(chǎn)生式。 S B1a1 （用產(chǎn)生式SB1a1） B2a2a1 （用產(chǎn)生式B1B2a2） Bn-1an-1a2a1 （用產(chǎn)生式Bn-2Bn-1an-1