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

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

2、): 用有限個規(guī)則描述無窮有限個規(guī)則描述無窮多字符串的集合n 自然語言描述(如：英語語法)；n 嚴格的形式規(guī)則描述（如：C語言文法、Pascal 語言文法）- 形式文法，形式文法， 形式語言形式語言2022年6月10日星期五南京航空航天大學計算機學院 胡軍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年6月10日星期五南京航空航天大學計算機學院 胡軍5問題的提出o 例2.2 根據例2.1中的各規(guī)則，下述的字符串 WHILE x5 DO x := (x+2) 是一個合法的語句;因為：n整個符合的定義結構；nx5是的一種；nx := （x+1）是的一種（從而也是的一種）；2022年6月10日星期五南京航空航天大學計算機學院 胡軍6語法樹(分析樹，Parser Tree)2022年6月10日星期五南京航空航天大學計算機學院 胡軍7問題的提出o 例2.3 用下述語法規(guī)則定義英語中的句子。 the a appl

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

5、右部。產生式的右部。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年6月10日星期五南京航空航天大學計算機學院 胡軍9文法表示方法的約定o 凡有關文法的例子，都遵循下述的約定：n大寫拉丁字母A,B,C,D,E和S等等表示變元變元，除非另做說明，S表示開始符號。n小寫拉丁字母a,b,c,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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