有限自動機(jī)理論CH2課件

1、第二章 形式語言簡介 形式語言和自動機(jī)理論中的語言是一個廣泛的概念。 一個字母表上的語言就是該字母表的某些字符串的集合。 語言中的字符串稱為該語言的句子語言的的定義可以從兩個方面進(jìn)行： ）從產(chǎn)生語言的角度； ）從接收(或識別)語言的角度。產(chǎn)生一個語言，目的就是根據(jù)語言中的基本句子和句子的形成規(guī)則，得到(產(chǎn)生)該語言所包含的所有句子。這是形式語言所研究的問題。接收一個語言，目的就是使用某種自動機(jī)模型來接收句子，該模型所接收的所有句子，也形成一個語言。這是自動機(jī)所研究的問題。 本章介紹形式語言的基本內(nèi)容。語言的形式定義設(shè)是一個字母表， L*, L稱為字母表上的一個語言, wL, w稱為語言L的一個

2、句子。2.1 例子語言括號匹配串的語言。 該語言是指所有的左括號和右括號相匹配的串的集合； ( )，( )，( )( )等等都是該語言的句子 )( ，( )等等不是該語言的句子。 如何產(chǎn)生這個語言呢？ 即如何產(chǎn)生該語言所有句子呢？實際上，就是需要給出語言中句子的構(gòu)造（形成）規(guī)則。遞歸定義提供了語言的良好的定義方式，使得語言中的句子的構(gòu)造規(guī)律較明顯?？梢允褂枚喾N方法描述構(gòu)造規(guī)則。自然語言的描述方式，采用如下的 遞歸規(guī)則：( )是該語言的最基本的句子；若S是句子,則(S)是句子；若S是句子,則SS是句子；這些規(guī)則稱為形成規(guī)則，根據(jù)這些規(guī)則，可以 (1)產(chǎn)生該語言的任意的句子； (2)判斷某個串是否

3、是該語言的句子。例如可以產(chǎn)生句子（） 而推斷串 （） 不是句子。規(guī)則(的個數(shù))是有限的，但可以產(chǎn)生無限個句子和長度無限的句子；因為規(guī)則是遞歸的。BNF的描述方式巴科斯和諾爾采用的巴科斯-諾爾范式（BNF-Backus-Naur Form）描述規(guī)則：:= ( ):=():= 使用尖括號“”包括起來的部分，作為一個整體來看待，表示某個語法成分 需要使用字母表中的字母來定義其構(gòu)成符號“:=”是BNF本身的符號（元符號），代表“定義為”或“是”。符號“( ”和“ )”是字母表的元素。Chomsky采用的符號化(形式化)的描述方式，運用如下的規(guī)則（這些規(guī)則被稱為產(chǎn)生式）： S( ) S(S) SSS “

4、”代表“定義為”或者“是” ， 它的左邊和右邊分別稱為該產(chǎn)生式的左邊和右邊根據(jù)產(chǎn)生式 可以生成任意句子； 可以判斷一個串是否為句子(語法分析)產(chǎn)生句子的過程 從S開始，利用產(chǎn)生式的右邊代替產(chǎn)生式的左邊（稱之為推導(dǎo)過程） 進(jìn)行多次推導(dǎo)，可以得到括號匹配的的句子。例:句子( )( )( )的推導(dǎo)過程 S =SS =(S)S =( )S =( )(S) =( )(SS) =( )( )S) = ( )( )( ) 產(chǎn)生式的個數(shù)是有限的，規(guī)則是遞歸的，因而所有的小括號匹配的串，都可以由產(chǎn)生式產(chǎn)生； 它們組成的集合就稱為一個語言。S稱為非終結(jié)符，在推導(dǎo)過程中，可以被代替的符號。(和)稱為終結(jié)符，在推導(dǎo)過

5、程中，不可以被代替的符號。 是產(chǎn)生式系統(tǒng)的元符號，不屬于非終結(jié)符，也不屬于非終結(jié)符。例2-1：由偶數(shù)個0組成的串的語言。 規(guī)則的自然語言描述方式：00是該語言的基本的句子；若S是句子,則00S是句子。 形式化的描述方式： S00 S00S 問題：將產(chǎn)生式SSS換成S0S0或SS00或SSS是否還產(chǎn)生相同的語言？ 結(jié)論： 一個語言，可以使用不同的產(chǎn)生式組合來產(chǎn)生?？紤]由奇數(shù)個1組成串的語言（產(chǎn)生規(guī)則）例2-2 高級程序設(shè)計語言中的算術(shù)表達(dá)式(的語言)的產(chǎn)生。 自然語言的描述方式單個變量是最基本的句子；若E是一個句子，則EAE是一個句子（其中A代表運算符+、-、*、/）若E是一個句子，則(E)是句

6、子；形式語言的描述方式 E i （i代表單個變量） EEAE E(E) A+ A- A* A/思考：字母表為？ 若以A開始推導(dǎo)，則產(chǎn)生？其中 ： A+，A-，A*，A/ 四個產(chǎn)生式的左邊是相同的符號，可以合并為 A+|-|*|/ +、-、*、/ 稱為A的侯選式。 E i EEAE E(E)也可以記為： E i|EAE|(E)注意： 這組產(chǎn)生式?jīng)]有表示出運算符的優(yōu)先級。表示出運算符的優(yōu)先級的產(chǎn)生式： EE+T|E-T|T TT*F|T/F|F F(E)|i其中：E代表表達(dá)式，T代表項，F(xiàn)代表因子(E)代表的是帶小括號的表達(dá)式。表示：先算因子，再*、/，最后+、-。 如果使用%代表模運算(即取余數(shù)

7、運算)、使用代表指數(shù)運算，則有 EE+T|E-T|T TT*F|T/F|T%F|A AFA|F F(E)|i注意需要考慮運算的結(jié)合性： 是右結(jié)合的。例2-3 標(biāo)識符(以字母開頭的字母、數(shù)字的串)的產(chǎn)生(僅考慮小寫字母)。 從標(biāo)識符的形成角度考慮ILIILIIDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|9思考：上例是從標(biāo)識符的形成角度思考問題。從標(biāo)識符的定義角度考慮，則？注意 D0|1|2|3|4|5|6|7|8|9不能簡寫為 D0|9將I的定義加入到表達(dá)式中： EE+T|E-T|T TT*F |

8、T/F|F F (E)|I IL|IL|ID L D思考: 其他類型的表達(dá)式（如關(guān)系表達(dá)式等）的定義：、=、= 標(biāo)識符(以下劃線或字母開頭的字母、下劃線和數(shù)字的串)的產(chǎn)生。例2-4C語言中簡單變量的說明語句的定義。 C語言中的說明語句形式為： TYPE 變量名表； TYPE 變量名表； TYPE 變量名表；產(chǎn)生式為： SSS|P PT V； Tint|char|float VV,V|I IL|IL|ID L D思考PASCAL語言的簡單變量的說明語句的形成。 VAR 變量名表: TYPE; 變量名表: TYPE ; 變量名表: TYPE; 2.2 文法和語言的關(guān)系語言的定義文法的定義文法與語言

9、的關(guān)系再次強(qiáng)調(diào)： 語言就是字母表上的字符串組成的一個集合。 語言中的字符串稱為句子。 文法的作用就是產(chǎn)生一個語言。 有窮語言的表示較容易。 即使語言中的句子的組成沒有什么規(guī)律，也可以使用枚舉的方式列出語言中的所有句子。 對于無窮語言，需要使用有窮描述的方式表達(dá)。 需要從語言的句子的一般構(gòu)成規(guī)律去考慮問題。 從語言的有窮描述來表達(dá)語言的方法對大多數(shù)語言是有效的。 在（使用計算機(jī)）判斷一個字符串是否是某個語言的句子時(語法分析) 從句子和語言的結(jié)構(gòu)特征上著手是非常重要的。 對于語言，可以在字母表上，按照一定的構(gòu)成規(guī)則，根據(jù)語言的結(jié)構(gòu)特點，可以定義一個產(chǎn)生該語言的文法。 使用文法作為相應(yīng)語言的有窮描

10、述，不僅可以描述出語言的結(jié)構(gòu)特征，而且可以產(chǎn)生這個語言的所有句子。定義2-1 短語結(jié)構(gòu)文法(文法)的定義文法G是一個四元式， G=(，V，S，P) 是一個有限字符的集合(字母表)，它的元素稱為字母或者終結(jié)符； V是一個有限字符的集合-非終結(jié)符集合，它的元素稱為變量或者非終結(jié)符；短語結(jié)構(gòu)文法(文法)的定義 SV，稱為文法的開始符號； P是有序偶對(，)的集合，其中是集合(UV)上的字符串，但至少包含一個非終結(jié)符；是集合(UV)*的元素。 一般，將有序偶對(，)記為，稱為產(chǎn)生式； 如果有，稱之為空串產(chǎn)生式或者產(chǎn)生式。 如果有AB，稱之為單產(chǎn)生式。 一個產(chǎn)生式的左邊可能不只一個符號； 第一個產(chǎn)生式的

11、左邊只能有一個符號，就是開始符號S。文法的作用就是產(chǎn)生一個語言。約定：如果沒有特別說明,則 第一個產(chǎn)生式左邊的符號，就是開始符號，可以不為S； 大寫的英文字母代表非終結(jié)符； 小寫的英文字母a，b，c，d，e和數(shù)字代表終結(jié)符； 小寫的英文字母u，v，w，x，y，z代表 終結(jié)符串； 小寫的希臘字母，代表非終結(jié)符和終結(jié)符串； 推導(dǎo)（派生）的定義2-2 文法G，和是集合(UV)上的串 = pvr ，=pur(p和r可能同時為) 而vu是文法G的一個產(chǎn)生式,則稱可以直接推導(dǎo)出 ， 記為= ，既 pvr =pur。推導(dǎo)的實質(zhì) 產(chǎn)生式的右邊替換產(chǎn)生式的左邊 非終結(jié)符代表在推導(dǎo)的過程中可以被替代的符號， 終結(jié)

12、符代表在推導(dǎo)的過程中不可以被替代的符號。 推導(dǎo)的逆過程稱為歸約。 與pvr =pur對應(yīng)，稱串pur可以直接歸約成串pvr 記為pvr +z 表示y可以經(jīng)過多步推導(dǎo)出z，即 存在串的序列1，2，3 ，n ； 有y=1 ，z= n ， 且i=i+1；對所有ni1。任意步推導(dǎo)(包括0步) y=*z 表示y可以經(jīng)過任意步推導(dǎo)出z，即 y=z；或者 y=+z。思考：對于任意文法G： S=*S S=+S 一定都成立嗎？最左推導(dǎo)和最右推導(dǎo) 如果在推導(dǎo)的過程中，每一步都是將推導(dǎo)產(chǎn)生的串的最左邊的非終結(jié)符代替掉-最左推導(dǎo) 如果每一步都是將推導(dǎo)產(chǎn)生的串的最右邊的非終結(jié)符代替掉-最右推導(dǎo)(規(guī)范推導(dǎo))， 當(dāng)然，還有

13、其它方式的推導(dǎo)過程（例如混合） 而最左推導(dǎo)和最右推導(dǎo)是比較常用的推導(dǎo)方式。句型和句子 對于文法G，如果S=*，則稱是文法的一個句型， 若 *, 稱為句子。定義2-3 語言的定義 給定文法G，有開始符號S，則把S可以推導(dǎo)出所有句子的集合，稱為由文法產(chǎn)生的語言，記為L(G)，即 L(G)=|S=*，且*例文法 G=(,),S,S, S( ), S(S), SSS ) 產(chǎn)生語言 L(G)=w|w是括號匹配的串注意:文法G產(chǎn)生語言L，必須：G推導(dǎo)產(chǎn)生的所有句子都在L中L的任意一個句子都可以由G產(chǎn)生對于文法G=(，V，S，P)約定： 第一個產(chǎn)生式左邊的符號，就是開始符號（可以不是S）； 大寫的英文字母代

14、表非終結(jié)符。 對于文法（G），只需給出該文法的所有產(chǎn)生式即可。產(chǎn)生括號匹配語言的文法可以寫成 S( ) S(S) SSS 還可以再簡單寫成 S( )|(S)|SS 文法和語言的3類問題 已知文法,得到該文法產(chǎn)生的語言 已知語言,構(gòu)造產(chǎn)生該語言的某個文法 判斷一個語言是否由某一個文法產(chǎn)生關(guān)系1： 文法 SaSa|bSb|c| 產(chǎn)生的語言是什么？ S能夠產(chǎn)生的所有句子，需要考慮3個產(chǎn)生式所有可能使用情況 注意對稱性關(guān)系2：構(gòu)造產(chǎn)生語言L的文法。 L= wwT|wa,b,c+其中：wT是w的逆（反序）思考：產(chǎn)生下列語言的文法： L1=anbn|n0 L2=anbn|n0關(guān)系3： 文法 S0B|1A

15、A0|0S|1AA B1|1S|0BB是否產(chǎn)生的語言L： L=|0,1+， 且中有相同多的0和1？注意： 一個語言可以由多個不同的文法產(chǎn)生。 一個文法只能產(chǎn)生一個語言。例2-5 G1：S0|1|00|11 G2：SA|B|AA|BB A0 B1L(G1)=L(G2)=0,1,00,11文法等價 如果文法G1和文法G2產(chǎn)生同一個語言，則稱文法G1和G2是等價的文法。 L(G1)= L(G2)注意區(qū)別：文法G1和G2等價文法G1和G2相同。 2.3Chomsky對文法的分類 Chomsky對文法進(jìn)行了分類； 對語言的分類，是根據(jù)產(chǎn)生語言的文法的分類進(jìn)行的0型文法 對于一般的短語結(jié)構(gòu)文法(PSG)

16、G=(，V，S，P) G稱為0型文法，對應(yīng)的L(G)稱為0型語言或者短語結(jié)構(gòu)語言(PSL)、遞歸可枚舉集。1型文法 如果對于任意P，均有|成立，則稱G為1型文法，或上下文相關(guān)文法(CSG)。 對應(yīng)的L(G)稱為1型語言或者上下文相關(guān)語言(CSL)。1型文法1型文法產(chǎn)生式的標(biāo)準(zhǔn)形式為： yAzyz其中：AV； y,z(V)*， (V)+；1型文法 可以證明，任意的1型文法，都可以改造為1型文法的標(biāo)準(zhǔn)形式。2型文法 如果對于任意P，均有|且V成立，則稱G為2型文法，或上下文無關(guān)文法(CFG) 對應(yīng)的L(G)稱為2型語言或者上下文無關(guān)語言(CFL)。3型文法 如果對于任意P，具有形式 Aw，AwB其

17、中，A，BV，w+ 則稱G為3型文法，或右線性文法 RLG，也可稱為正則文法RG。 對應(yīng)的L(G)稱為3型語言或 右線性語言RLL或 正則語言RL。 四類文法和對應(yīng)的四類語言之間是真包含關(guān)系。 思考 如果文法G有產(chǎn)生式，則G是 型文法?文法分類判斷方法： 文法G=(，V，S，P)，則 1) G是短語結(jié)構(gòu)文法； 2) 如果文法G的所有產(chǎn)生式的左邊長度小于等于右邊長度部分，那么G是上下文相關(guān)文法； 3) 如果上下文相關(guān)文法G的所有產(chǎn)生式的左邊都是一個非終結(jié)符，那么G是上下文無關(guān)文法； 4) 如果上下文無關(guān)文法G的所有產(chǎn)生式的右邊最多只有一個非終結(jié)符 且該非終結(jié)符號只能出現(xiàn)在最右邊，那么G是正則文法

18、。文法G: S01|101S是RG，CFG，CSG和PSG文法G： SAaS|AS Aa|b|c|d是CFG，CSG和PSG，但不是RG。文法G SaB aBab是CSG和PSG，但不是CFG和RG。文法G S aB aBab aBa是PSG，但不是CFG、RG和CSG。 形如的產(chǎn)生式稱為空產(chǎn)生式，也可稱為產(chǎn)生式。 CSG、CFG和RG，都不能含有空產(chǎn)生式，所以任何CSL、CFL和RL中都不包含(空句子)。 如果允許在CSG、CFG和RG中含有空產(chǎn)生式， 也就允許CSL、CFL和RL中包含空句子。 一般地，如果語言L沒有空句子，則 文法中增加產(chǎn)生式 S 就可以產(chǎn)生空句子。文法擴(kuò)充分類： 設(shè)文法

19、G=(，V，S，P) 如果S不出現(xiàn)在任何產(chǎn)生式的右部，則(1) 若G是CSG G=(，V，S，PS)仍然為CSG； L(G) 是CSL。(1) 若G是CFG G=(，V，S，PS)仍然為CFG；L(G) 是CFL。 (1) 若G是RG G=(，V，S，PS) 仍然為RG； L(G) 是RL。思考 為什么要有條件 S不出現(xiàn)在任何產(chǎn)生式的右部？設(shè)正則文法RG：Sab|aS，則 L(G)=a+bG：Sab|aS|L(G)=a+b, , a+增加了空句子，但多產(chǎn)生句子a+定理2-1 文法G=(，V，S，P) ，存在與G同類型的文法 G=(,V, S P) ，使得 L(G)=L(G)且S不出現(xiàn)在G的任何

20、產(chǎn)生式右部 證明： 先根據(jù)G構(gòu)造滿足條件的G，然后證明兩者等價。 構(gòu)造G=(，VS,S,P)其中P=PS|SP G與G有相同的類型。G與G等價 即證明L(G)=L(G) 需要證明 L(G) L(G) L(G) L(G)特殊情況 如果S不出現(xiàn)在P中任何產(chǎn)生式的右邊，則 G=G 思考 文法的S不出現(xiàn)在產(chǎn)生式的右部 那么，S的作用是什么？下列命題成立 有語言L，設(shè)置L = L (1)若L是CSL，則L仍然是CSL。 (2)若L是CFL，則L仍然是CFL。 (3)若L是RL，則L仍然是RL。證明： 證明第(1)個命題， (2)(3)同理可證。證明 設(shè)L是CSL，則存在一個 CSG=(，V，S，P) 使

21、得 L(G)=L。 設(shè)S不出現(xiàn)在G的產(chǎn)生式右部。構(gòu)造 G=(,V,S,PS)G也是CSG。 S不出現(xiàn)在G中產(chǎn)生式的右部 增加的S，不可能出現(xiàn)在非空句子的推導(dǎo)中，則 L(G)=L(G) L(G)是CSL。結(jié)論 增加空句子不影響語言的類型。同理刪除空句子也不影響語言的類型。下列命題成立有語言L，L = L- (1)若L是CSL，則L仍然是CSL。 (2)若L是CFL，則L仍然是CFL。 (3)若L是RL，則L仍然是RL。證明： 證明第(1)個命題， (2)(3)同理可證。證明設(shè)L是CSL，則存在一個 CSG=(，V，S，P) 使得 L(G)=L。如果 L L-=L L- 是CSL。如果L 設(shè)S不出

22、現(xiàn)在G的產(chǎn)生式的右部。 構(gòu)造=(,V,S,P-S)， G也是CSG。 S不出現(xiàn)在G產(chǎn)生式的右部 去掉S,則不影響任何非空句子的推導(dǎo)， L(G)=L(G)-。 L(G)是CSL。 除了生成空句子外，空產(chǎn)生式可以不用于其他句子的推導(dǎo)中。 空句子在一個語言中的存在并不影響該語言的有窮描述。 如果允許CSG,CFG,RG包含一般的-產(chǎn)生式 1)可能對問題的處理提供方便。 2)編譯理論中(無回溯的)自上而下分析法需要一般的-產(chǎn)生式。 L(G)=w|w0,1+,且w以0開始 G可以為：S0|0A A0|1|0A|1A 其中： A產(chǎn)生0,1+或S？ A|0A|1A 其中：A產(chǎn)生0,1* 2.4文法產(chǎn)生語言例

23、 文法 S0S S0產(chǎn)生語言L=0n|n0分析 如果開始使用第2個產(chǎn)生式S0，則S=0，就不能再往下進(jìn)行推導(dǎo)了。 產(chǎn)生基本句子0；若使用產(chǎn)生式S0S，n-1次后，則 S=0S=00S=000S=+0n-1S使用S0，則S=+0n 這對于任何n1都是成立的； 總之，該文法產(chǎn)生語言L=0n|n0。定義2-7 遞歸文法 一個上下文無關(guān)文法G，AV 如果 A =+A ，則該文法稱為遞歸的文法；(A:遞歸非終結(jié)符) 遞歸分為直接和間接遞歸。 若A =A 則稱為直接遞歸的非終結(jié)符。 直接遞歸可以從產(chǎn)生式判斷。 間接遞歸需要根據(jù)推導(dǎo)過程才能進(jìn)行判斷。思考 是否可以將間接遞歸轉(zhuǎn)換為直接遞歸？ 如何進(jìn)行轉(zhuǎn)換？

24、基本思路： 將推導(dǎo)過程直接反映在產(chǎn)生式中 方法： 代入法 一個上下文無關(guān)文法的產(chǎn)生式的個數(shù)總是有限的。 如果該文法是遞歸文法，則該文法就能夠產(chǎn)生一個無窮語言。 若一個上下文無關(guān)文法不是遞歸的文法，則 該文法產(chǎn)生有窮語言。注意 特殊形式的產(chǎn)生式 AA 是遞歸的，可以反復(fù)利用任意多次，但對于無窮語言的產(chǎn)生，沒有任何作用定義2-8 空串產(chǎn)生式的定義 形如A的產(chǎn)生式，稱為上下文無關(guān)文法的空串產(chǎn)生式，或產(chǎn)生式； 空串產(chǎn)生式的作用就是在推導(dǎo)的過程中，對于某個句型，省略掉能夠產(chǎn)生的非終結(jié)符號。 若某個上下文無關(guān)文法G有S，則 該L(G)一定包含空句子例文法 S0S S該文法產(chǎn)生語言L=0n|n0。思考： 該

25、文法是 ？型文法分析 如果開始使用第2個產(chǎn)生式S，則S=，就不能再往下進(jìn)行推導(dǎo)了， 則產(chǎn)生空句子； 如果開始使用產(chǎn)生式S0S，n次后， S=0S=00S=000S=+0nS 最后，使用S，則S=+0n 這對于任何n1都是成立的；總之，該文法產(chǎn)生語言L=0n|n0例 文法 SaSb Sab產(chǎn)生語言 L=anbn|n0例文法 SaS SbS S產(chǎn)生語言 L=a，b*例 字母表a，b上所有對稱的非空串組成的語言(沒有中心點) 構(gòu)造文法產(chǎn)生該語言分析 aa和bb是最基本的句子。 如果S是句子，則aSa和bSb是句子得到文法： Saa Sbb SaSa SbSb思考(1)文法 SaSa SbSb Sa

26、Sb產(chǎn)生的語言是什么？思考(2)文法 SaSa SbSb S產(chǎn)生的語言是什么？練習(xí)：構(gòu)造文法，產(chǎn)生(1)字母表a，b上所有對稱的非空串組成的語言。(2) L=wdwT|wa,b,c+。(3) L=anbn|n=0。一般對任意的a,b+，可以使用Aab|aAb來產(chǎn)生anbn|n0；對任意的a,b+，可以使用Aa|b|aA|bA來產(chǎn)生a，b+；對任意的a+，可以使用Aa|aA來產(chǎn)生an|n0；對任意的a，b+，可以使用 AaAa|bAb來產(chǎn)生 wAwT|wa,b+注意：不能使用 Aa2代表 Aaa不能使用 Aan(n1) 或 Aa+來代表 A可以產(chǎn)生任意多個a。思考：字母表為0，1語言的特性及產(chǎn)生

27、語言的文法 (1) x | x=xT , x (2) x| x=xT , x + (3) xxT | x + (4) xxT | x * (5) x0 xT | x + (6) xwxT | x, w + (7) xxTw | x, w + 構(gòu)造文法產(chǎn)生所有的無符號整數(shù)。 無符號整數(shù)是由0，1,9中的10個數(shù)字符號組成的，但不允許以0開始。 NAM|0 A1|2|3|4|5|6|7|8|9 M|0M|1M|2M|3M|4M|5M|6M|7M|8M|9M例2-11構(gòu)造文法G，產(chǎn)生語言w|w是實數(shù)略。例2-12 S0B|1A A0|0S|1AA B1|1S|0BB證明：L(G)=|0，1+，且中有

28、相同多的0和1。證明提示： 使用數(shù)學(xué)歸納法（句子長度）證明過程 略。根據(jù)下推自動機(jī)0分析 所有產(chǎn)生式的的使用情況: 順序和次數(shù)思考： 上下文相關(guān)上述文法的后3個產(chǎn)生式 bBbb bCbc cCcc是否可以改為 Bb Cc上例還可以簡化為： Sabc|aSBc cBBc bBbb 文法的產(chǎn)生式的左邊可以有多個符號思考：補(bǔ)充文法G使得L(G)= anbncn|n0 SaBSc SaBc Ba? 練習(xí)：構(gòu)造文法G，使得 L(G)=anb2n|n=1 L(G)=am+1b2m+1|m=0 L(G)=anb2n-1|n=12.5 推導(dǎo)樹對于上下文無關(guān)文法， 利用推導(dǎo)樹也可以表示句型的產(chǎn)生過程。例-16

29、S0B|1A A0|0S|1AA B1|1S|0BB對于串0011的產(chǎn)生過程：推導(dǎo)過程最左推導(dǎo)： S=0B=00BB=001B=0011 最右推導(dǎo)： S=0B=00BB=00B1=0011推導(dǎo)樹表示推導(dǎo) S 0 B 0 B B 1 1無用非終結(jié)符一個無關(guān)文法G,AV 如果A不出現(xiàn)在任何形如 S=*uAv=+uwv的推導(dǎo)之中-A為無用非終結(jié)符。其中：u ，w ，v *。有用非終結(jié)符A，必須同時滿足:(1) A必須出現(xiàn)在某個句型中；(2)從A開始，能夠產(chǎn)生終結(jié)符號串無用的產(chǎn)生式 如果一個產(chǎn)生式(產(chǎn)生式的左邊或右邊)包含有無用的非終結(jié)符，則該產(chǎn)生式就是無用的產(chǎn)生式。 應(yīng)該將無用的產(chǎn)生式刪除。思考如果

30、文法G的開始符號S是無用的非終結(jié)符號，則L(G)=?思考判斷A是有用的非終結(jié)符號的算法。 請參見參考文獻(xiàn) 形式語言與自動機(jī)理論 （蔣宗禮 姜守旭 清華大學(xué)出版社）2.6 空串定理 上下文無關(guān)文法G ，存在一般的空串產(chǎn)生式A，則存在另一個上下文無關(guān)文法G1，使得：L(G)=L(G1)；若L(G) ，則G1中沒有任何空串產(chǎn)生式（S1就是S）； 若L(G)，則G1中僅有一個空串產(chǎn)生式S1，且S1不出現(xiàn)在G1的產(chǎn)生式的右邊。證明（2） 因為L(G)，對于任意CV，考慮它的任意產(chǎn)生式Cw（w不為空串），w中非終結(jié)符分為A1，A2，Ak，B1，B2，Bj， 對于Ai， 有 Ai 1ik 將Cw改造為Cw

31、w是通過0步，1步，k步刪除w中的Ai而得到的，w共有2k個。 最后，去掉所有的空串產(chǎn)生式和無用的產(chǎn)生式就得到G1。 考慮G產(chǎn)生句型的推導(dǎo)樹T: 若的推導(dǎo)中使用了空串產(chǎn)生式，則樹T中有以為標(biāo)志的葉節(jié)點， 刪除樹T中的所有產(chǎn)生的子樹，得到樹T1，而它剛好是文法G1產(chǎn)生串的推導(dǎo)樹，所以，L(G)=L(G1)。例文法： 改造成等價的G：SABCD SACDCRS CSB AaAa DdDd SdR Sd 證明（3） 假設(shè)L(G)，則要增加新的開始符號S和兩個產(chǎn)生式 SS， S；再消除其余的空串產(chǎn)生式，即可。2.7 消除左遞歸在某些情況下,需要消除一個無關(guān)文法中的左遞歸。遞歸的作用是產(chǎn)生無窮的語言，消

32、除左遞歸，只是將左遞歸改造為右遞歸。左遞歸包括直接的和間接的左遞歸。2.7.1 消除直接左遞歸直接左遞歸的產(chǎn)生式形式為 AAv 其中：AV，v(UV)+。遞歸的產(chǎn)生式可以產(chǎn)生串v的任意次連接。 假設(shè)文法G的產(chǎn)生式形式為： AAv|w其中: v,w(UV)+， 且w不包含A對于A，有 A=*wv*增加B V，構(gòu)造無左遞歸文法： AwB|w BvB|v 右遞歸則 A=*wv*或 （編譯采用的文法） AwB BvB|實際上，消除了產(chǎn)生式，就得 AwB|w BvB|v一般地，產(chǎn)生式的形式為： AAv1|Av2|Avn|w1|w2|wm對于A，有 A=*(w1|w2|wm)(v1|v2|vn)*增加一個

33、新的非終結(jié)符B，構(gòu)造無左遞歸文法：Aw1B|w2B|wmB|w1|w2|wmBv1B|v2B|vnB|v2|v2|vn某些文法可能沒有直接左遞歸，但可能會有間接左遞歸。 SAa ASb|b2.7.2 消除間接左遞歸（自學(xué)）G是一個上下文無關(guān)文法，首先使用空串定理；然后將文法G中的所有非終結(jié)符按任一順序排列為A1，A2，An，根據(jù)下列算法消除可能存在的間接左遞歸。for i：=1 to n do begin for j：=1 to i-1 do begin 將Ai Ajw的產(chǎn)生式改寫為： Aiv1w|v2w|vkw ； (v1，v2，vk是Aj的侯選式) end 消除Ai產(chǎn)生式的直接左遞歸； e

34、nd最后，刪除無用的產(chǎn)生式，就可以得到?jīng)]有間接左遞歸的文法。該算法思想是將推導(dǎo)過程中可能出現(xiàn)的左遞歸，在文法的產(chǎn)生式中就體現(xiàn)出來，產(chǎn)生式的改寫實際上是推導(dǎo)的體現(xiàn)-用Aj的侯選式將Aj代替掉。為方便實現(xiàn)，將上述算法進(jìn)行改寫。G是一個上下文無關(guān)文法，將文法G中的所有非終結(jié)符按任一給定的順序排列為A1，A2，An那么，文法的每個產(chǎn)生式是AiAjw的形式（對于Aiaw形式的產(chǎn)生式，不用考慮，因為它不會導(dǎo)致左遞歸的出現(xiàn)）.而i和j的大小關(guān)系只可能有3種情況：AiAjw ij 稱該產(chǎn)生式是向下的；這類產(chǎn)生式需要替代，用Aj的侯選式將Aj替掉，若出現(xiàn)了直接左遞歸，還需要將直接左遞歸消除；首先考慮非終結(jié)符A1

35、：A1Ajw 1j 產(chǎn)生式是向上的 1=j 該產(chǎn)生式是直接左遞歸的；消除直接左遞歸對于非終結(jié)符A2:A2Ajw 2j 該產(chǎn)生式是向下的；這類產(chǎn)生式需要替代，對于非終結(jié)符An： AnAjw n=j 消除直接左遞歸； nj 向下的；這類產(chǎn)生式需要需要替代，用Aj的侯選將Aj替換掉，若出現(xiàn)了直接左遞歸，還需要將直接左遞歸消除；最后，刪除多余的產(chǎn)生式，得到的文法就沒有了左遞歸，包括直接和間接的左遞歸。2.8 上下文無關(guān)文法的另一種表示文法存在另外一種表示方法： 使用表示* ； 使用表示的出現(xiàn)可有可無(等價于)左遞歸的產(chǎn)生式 Aa|b|Aw改寫成 A(a|b)w右左遞歸的產(chǎn)生式 Aa|b|wA改寫成：

36、Aw(a|b)例2-18 標(biāo)識符可定義為 IL IIL IID La|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 D0|1|2|3|4|5|6|7|8|9改寫成ILL|DLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|92.9 語言之間的運算及運算封閉性 對簡單語言進(jìn)行語言的運算，可以產(chǎn)生復(fù)雜語言。語言對運算的封閉性 如果任意的、屬于某一語言類的語言在某一特定運算下所得到的語言仍然是同類語言: 該語言類對此運算具有封閉性有效封閉性 根據(jù)多個語言

37、的(文法)描述, 若可以構(gòu)造出給定運算下所獲得的同類語言的(文法)描述 此語言類對該運算是有效封閉的(有效封閉性)。問題本質(zhì)存在文法G1和G2 L1=L(G1)；L2=L(G2)需要構(gòu)造文法G，使得 L(G)是對L1和L2是進(jìn)行某種運算后得到的語言。語言的有效封閉性可以 證明某些語言屬于某類語言， 從簡單語言構(gòu)造復(fù)雜的同類語言。2.9.1 語言之間的基本運算 若語言L1和L2是字母表1和 2上的兩個語言，定義 語言L1和L2的聯(lián)合運算為： L1UL2=w|wL1或者wL2思考新語言的字母表是？連接語言L1和L2的連接運算為： L1L2= w|w=w1w2，w1L1，w2L2迭代 語言L1的迭代

38、運算(或星運算，閉包運算)為： L1*=w| w= w1w2wm， wiL1，m0 =L1n 對n0 注意語言L1=an|n0，L2=bn|n0， 則 L1L2是 anbm|n,m0 而不是 anbn|n0定理2-7 i (i=0，1，2，3)型語言對聯(lián)合，連接和迭代運算有效封閉證明： 設(shè)參加運算的語言L1和L2分別是字母表1和 2上的語言。產(chǎn)生L1的文法 G1=（1，V1，S1，P1）產(chǎn)生L2的文法 G2=（2，V2，S2，P2）即L1=L(G1)；L2=L(G2)假定 12= V1V2= SV1 SV2設(shè)置 =12 V=V1UV2US聯(lián)合運算構(gòu)造 G3=（，V，S，P3）其中: P3=SS

39、1USS2UP1UP2聯(lián)合運算對于i=0，1，2 若G1和G2是i型文法，則G3依然。 顯然，L(G3)=L(G1)UL(G2)， 0、1、2型語言類對于聯(lián)合封閉。聯(lián)合運算若G1和G2是3型文法，G3 ? 構(gòu)造文法G4=（，V，S，P4） 其中P4為： Sw1|S1w1在P1中U Sw2|S2w2在P2中UP1U P2聯(lián)合運算則G4是RG，且L(G4)=L(G1)UL(G2)。所以3型語言對于聯(lián)合封閉。聯(lián)合運算實際上，G4的構(gòu)造方法也適合于 0、1、2型文法。思考 特殊性與一般性連接運算構(gòu)造G5=（，V，S，P5） 其中P5= SS1S2 U P1 U P2對于i=0，1，2 若G1和G2是i

40、型文法，則G5依然連接運算S1=*w1 L1 S2=*w2 L2則 S=S1S2=* w1w2 則 L(G5)=L(G1)L(G2)；0、1、2型語言對連接封閉。連接運算對于3型文法：SS1S2 ？ 構(gòu)造G6=(，V1UV2，S1，P6 )其中P6為： AwS2|Aw在P1中 - Aw U P1 U P2連接運算將每個形如Aw的產(chǎn)生式，改寫為 AwS2則從S1=+ r1r2rkA =r1r2rkwS2=其中，r1r2rkw L1連接運算L(G6)=L(G1)L(G2)； 3型語言對連接封閉。注意：若P1中有空串產(chǎn)生式，則要先消除空串產(chǎn)生式連接運算若G1和G2是0型或1型文法， 而 12（包括1

41、=2 ）則 文法G5可能會有問題。連接運算文法G1：S1b文法G2：S2c|bA|A A a bAbb則L(G1)=b，L(G2)=c,a,ba,bb L(G1)L(G2)=bc,ba,bba,bbb連接運算 存在 S=S1S2=bS2=bA = bb 不是語言L(G1)和L(G2)的連接后的句子思考產(chǎn)生問題的原因是？ 該問題產(chǎn)生的原因是S1和S2產(chǎn)生的串發(fā)生了串道(cross)。 即文法G1可能將S2產(chǎn)生的串作為下文，文法G2可能將S1產(chǎn)生的串作為上文。思考串道是終結(jié)符號還是非終結(jié)符號？ 終結(jié)符號解決串道問題的方法 將終結(jié)符號變換為不一致的描述連接運算解決串道問題，將復(fù)制為和 令=x|x =

42、x|x連接運算將P1中的x用x代替,得到P將P2中的x用x代替,得到P連接運算構(gòu)造G7=(,V U U,S，P7) 其中P7為： SS1S2 U PU P U xx|xUxx |x則L(G7)=L(G1)L(G2)。文法G1：S1b文法G2：S2c|bA|A Aa bAbb P7 為 SS1S2 S1b S2c|bA|A Aa bA bb bb cc bb S=S1S2 =b S2 =bS2 =?迭代運算（一元運算）基本思路： 空句子, 迭代 若S|SS1 S 在產(chǎn)生式右邊，封閉性存在問題 迭代運算考慮文法 S|S SS1|S1S則S推導(dǎo)出和S1n(n1)迭代運算構(gòu)造G8=(,V1US，S,S

43、,P8) 其中P8為：S|SUSS1|S1SUP1迭代運算 若G1是2型文法，則G8也是2型文法； 且 S=*L(G1)* 所以2型語言對迭代封閉。 若G1是0、1型文法， 文法G8可能會有同樣的串道問題。如 S1abS1|S1a bS1bb S1ac迭代運算 首先,消除G1中的空串產(chǎn)生式，將復(fù)制為和, 構(gòu)造P和P，構(gòu)造G= (,V1UU S-S1,S,P)將S1改寫SG= (,V1UU S-S1,S,P)將S1改寫S迭代運算構(gòu)造G9=(, V1 U U U S,S, S1，S2, S，P9)其中P9為： S|S1|S2 U S1S|SS2 U S2S | S S1 UPUP U xx|xUx

44、x |x為避免串道，需要S和 S 交替出現(xiàn)，有兩種可能： S1推導(dǎo)出S S S S S S S2推導(dǎo)出S S S S S S注意:原來的S1已經(jīng)改寫為S和 S 迭代運算則L(G9)=L(G1)*；所以0型和1型語言對迭代封閉。迭代運算對于3型文法，引入新的開始符號S和S來產(chǎn)生空串（若在P1中有S1，則刪除S1）增加Sr (其中S1r 在P1中) 以便開始推導(dǎo)(r=wB 或 r=w)迭代運算對于每個形如Aw的產(chǎn)生式，增加 AwS1（不刪除Aw） 從S開始，可以推導(dǎo)出句型 r1r2rkA 其中：r1，r2，rk L1可以在推導(dǎo)出r1r2rkw時停止， 也可以從r1r2rkwS1開始推導(dǎo)出另一個更長

45、的串， 直至L(G1)*迭代運算G1是3型文法，構(gòu)造 G10=（，V1US，S，P10）其中P10為：迭代運算 S U (P1 - S1 ) U Sr | S1r在P1中 U AwS1|若Aw(包括Sw)G10也是RG，且L(G10)=L(G1)*；所以3型語言對迭代封閉。結(jié)論不論字母表 12 或 12（包括1=2 ）四類語言對聯(lián)合、連接和迭代運算是有效封閉的。 2.9.3 語言之間的其他運算定理2-8 正則語言對于補(bǔ)和交運算是封閉的。該定理的證明需要使用自動機(jī)的知識，留待今后證明。定理2-9上下文無關(guān)語言對于補(bǔ)和交運算不是封閉的。證明：舉一個反例即可上下文無關(guān)語言 L1=anbncm|n,m

46、0上下文無關(guān)語言 L2=aibkck|i,k0它們的交集為L=anbncn|n0不是上下文無關(guān)語言（是一個上下文相關(guān)語言）。語言，還有一個有用的運算置換。定義2-15 置換的定義一個映射g為置換映射： X*Y* (X和Y當(dāng)作字母表) 若g()=，且對n1； g(w1w2wn)=g(w1)g(w2)g(wn) 其中 g(wi)=yY*或 g(wi)=y1 ,y2 ， 特別地，若g(wi)=yY* 則g稱為同態(tài)。直觀上看，同態(tài)僅僅只改變了成分的名字，除非同態(tài)把元素a映射成為或者是一個串。g(L)若L是字母表上的一個語言，則 g(L)=Ug(w) 其中wL。 g(a*) = g()Ug(a)Ug(a

47、a)U Ug(aa)=(g(a)*。 g(w*)= (g(w)* g(L*)= (g(L)*例=a，b，g(a)=0*，g(b)=1；若語言L=(aba)*，則 g(L) =(0*10*)*。定理2-10上下文無關(guān)語言對于置換映射是封閉的。證明：2型文法G=(,V,S,P)產(chǎn)生語言L g是一個置換映射： g(x)=Lx 其中，x構(gòu)造，將文法G改造為 G=(Y，V U ，S，P) 將G產(chǎn)生式中的終結(jié)符x替換為x 再增加產(chǎn)生式，使得每個 x=+ Lx 得到P若文法G產(chǎn)生句子x1x2xn 則文法G產(chǎn)生句型x1x2xn 再得到句子Lx1Lx2Lxn。所以文法G產(chǎn)生語言g(L)，也是上下文無關(guān)的語言。 文法G:S aSb|ab L(G)=anbn若 g(a)=0*，g(b)=1構(gòu)造文法：S aS b |ab a |0 a b 1 產(chǎn)生語言(0*1+)定理2-11正則語言對于置換映射是封閉的。證明： 略。2.10 正則表達(dá)式和正則集有效自動化是計算學(xué)科的重點問題有效自動化的基礎(chǔ)是實現(xiàn)對問題的恰當(dāng)?shù)男问交枋?。對于正則的語言，可以使用正則表達(dá)式來表示。優(yōu)勢這種表達(dá)形式還更接近語言的集合表示和語言的計算機(jī)表示。語言的集合表示形式使得更容易理解和使用；而適合計算機(jī)的表示形式又使得它更容易被計算機(jī)系統(tǒng)處理。本