形式語(yǔ)言與自動(dòng)機(jī)課件——語(yǔ)言及文法

1、1College of Computer Science & Technology, BUPT第二章第二章 語(yǔ)言及文法語(yǔ)言及文法n主要內(nèi)容主要內(nèi)容：n定義形式語(yǔ)言的術(shù)語(yǔ)定義形式語(yǔ)言的術(shù)語(yǔ)n給出文法的定義和文法的分類給出文法的定義和文法的分類n要求掌握：要求掌握：n語(yǔ)言和文法的形式定義語(yǔ)言和文法的形式定義nCHOMSKY文法體系的分類。文法體系的分類。2College of Computer Science & Technology, BUPT第一節(jié)第一節(jié) 語(yǔ)言的定義與運(yùn)算語(yǔ)言的定義與運(yùn)算一、一、語(yǔ)言的一些術(shù)語(yǔ)：語(yǔ)言的一些術(shù)語(yǔ)：n 字母表：字母表： 字符的有限集合，記為字符的有限

2、集合，記為T。 n字符串：字符串： 由字母表由字母表T中的字符構(gòu)成的序中的字符構(gòu)成的序列稱字母表列稱字母表T上的字符串（句子）。上的字符串（句子）。n 常記為常記為u,v,w,x,y,z；n 常用常用a,b,c,d 標(biāo)識(shí)單個(gè)字符。標(biāo)識(shí)單個(gè)字符。3College of Computer Science & Technology, BUPT字字 母母 表表 （Alphabet） 概念概念 形式符號(hào)的集合形式符號(hào)的集合 記號(hào)記號(hào) 常用常用 T、 表示表示 舉例舉例- 英文字母表英文字母表 a, b, , z, A, B , , Z - 英文標(biāo)點(diǎn)符號(hào)表英文標(biāo)點(diǎn)符號(hào)表 , ; : . ? ! “

3、 ” ( ) - 漢字表漢字表 , 自自, , 動(dòng)動(dòng) , , 機(jī)機(jī), - 化學(xué)元素表化學(xué)元素表 H, He, Li, , - T = a, n, y, 任任,意意 4College of Computer Science & Technology, BUPT字字 符符 串串 （string） 概念概念 字母表字母表 T 上的一個(gè)上的一個(gè)字符串字符串（簡(jiǎn)稱（簡(jiǎn)稱串串），或稱為），或稱為 字字（word），），為為 T 中字符構(gòu)成的一個(gè)有限序列。中字符構(gòu)成的一個(gè)有限序列。 空串空串（empty string）, 用用 表示，不包含任何表示，不包含任何 字符。字符。 舉例舉例 設(shè)設(shè) T =

4、a, b ，則則 , a, ba, bbaba 等都是串等都是串 字符串字符串 w 的的長(zhǎng)度長(zhǎng)度，記為，記為 w ，是包含在是包含在 w 中字符的中字符的個(gè)數(shù)個(gè)數(shù) 舉例舉例 = 0， bbaba = 5 ai 表示含有表示含有i個(gè)個(gè)a的字符串的字符串5College of Computer Science & Technology, BUPT 連接（連接（concatenation） 設(shè)設(shè) x, y為串為串, 且且 x a1a2 am, y b1b2 bn, 則則 x 與與 y 的連接的連接 x y a1a2 am b1b2 bn 連接運(yùn)算的性質(zhì)連接運(yùn)算的性質(zhì) - ( x y ) z

5、x（ y z ）- x x x - x y x + y 關(guān)關(guān) 于于 字字 符符 串串 的的 運(yùn)運(yùn) 算算6College of Computer Science & Technology, BUPT 其它其它 如如 取頭字符取頭字符，取尾部取尾部，子串匹配子串匹配 等等n 設(shè)設(shè)1, 2, 3是字母表是字母表T上的字符串，稱上的字符串，稱1是字符是字符串串12的前綴，的前綴，2是字符串是字符串12的后綴，且的后綴，且2是字符串是字符串123的子串。的子串。 n 空串是任何字符串的前綴，后綴及子串。空串是任何字符串的前綴，后綴及子串。n 例例：abc的前綴的前綴 a ab abc . 后綴后

6、綴 c bc abc . 子串子串 a b c ab bc abc , 即一個(gè)字符串可以看作是多個(gè)字符串的連接。即一個(gè)字符串可以看作是多個(gè)字符串的連接。 關(guān)關(guān) 于于 字字 符符 串串 的的 運(yùn)運(yùn) 算算7College of Computer Science & Technology, BUPTn 字符串字符串的逆用的逆用 表示。表示。 是字符是字符串串的倒置。的倒置。= b1b2bn = bnbn-1b2b1n 空串空串的逆還是的逆還是8College of Computer Science & Technology, BUPT字字 母母 表表 的的 冪冪 運(yùn)運(yùn) 算算 冪運(yùn)算冪

7、運(yùn)算 設(shè)設(shè) T 為字母表，為字母表，n 為任意自然數(shù)，為任意自然數(shù)， 定義（定義（1） T0 = （2）設(shè)）設(shè) x Tn-1，a T， 則則a x Tn （3） Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 閉包閉包 T* = T0 T1 T2 閉包閉包 T+ = T1 T2 T3 T* = T+ ， T+ = T* - - 9College of Computer Science & Technology, BUPT閉包的物理意義閉包的物理意義 T的星號(hào)閉包的星號(hào)閉包T*：字母表T上的所有字符串和空串的集合。 T的正閉包的正閉包T+：字母表T上的所有字符串構(gòu)成的集

8、合。T*= T+ 舉例舉例 設(shè)設(shè) T = 0，1 ，則則 T0 = ， T1 = 0，1 ， T2 = 00，01 ，10 ，11 ， T* = ，0，1，00，01 ，10 ，11， T+ = 0，1，00，01 ，10 ，11， 10College of Computer Science & Technology, BUPT語(yǔ) 言 （Languages） 概念概念 設(shè)設(shè) T 為字母表，則任何集合為字母表，則任何集合 L T* 是是字母字母表表T上的上的一個(gè)語(yǔ)言（一個(gè)語(yǔ)言（language） 舉例舉例 - 英文單詞集英文單詞集 , English, , words , - C 語(yǔ)言程

9、序集語(yǔ)言程序集 字母表？字母表？- 漢語(yǔ)成語(yǔ)集漢語(yǔ)成語(yǔ)集 , 馬到成功馬到成功, - 化學(xué)分子式集化學(xué)分子式集 , H2O, , NaCl , - any, 任意任意 11College of Computer Science & Technology, BUPT語(yǔ) 言 （Languages）舉例舉例：設(shè)：設(shè)T = a，b 則則 L1 = anbn | n1 L3 = bk | k 是質(zhì)數(shù)是質(zhì)數(shù) L2 = 只有一個(gè)空句子的語(yǔ)言只有一個(gè)空句子的語(yǔ)言 L4 = = 空語(yǔ)言空語(yǔ)言 均為字母表均為字母表T上的語(yǔ)言。上的語(yǔ)言。由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)于集合的運(yùn)算可由語(yǔ)言的定義知語(yǔ)言是集合，對(duì)

10、于集合的運(yùn)算可應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。應(yīng)用于對(duì)于語(yǔ)言的計(jì)算。如并，交，補(bǔ)，差。12College of Computer Science & Technology, BUPT語(yǔ)言的基本運(yùn)算 語(yǔ)言的積：語(yǔ)言的積：兩個(gè)語(yǔ)言L1 和L2的積L1 L2是由L1和L2中的字符串連接所構(gòu)成的字符串的集合。即L1中所有字符串分別與L2中的字符串連接得到的集合。設(shè)T=a, b， L1和 L2是T上的語(yǔ)言。 L1 =ab, ba L2 =aa, bb則 L1 L2 =abaa, abbb, baaa, babb L2 L1 =aaab, aaba, bbab, bbban L1 L2 L

11、2 L1 語(yǔ)言的積不可交換。語(yǔ)言的積不可交換。13College of Computer Science & Technology, BUPT語(yǔ)言的基本運(yùn)算 語(yǔ)言的冪：語(yǔ)言的冪：語(yǔ)言的冪可歸納定義如下語(yǔ)言的冪可歸納定義如下: L0 = Ln = L Ln-1 = Ln-1 L n 1上例中，上例中，L12 =abab, abba, baab, baba L22 =aaaa, aabb, bbaa, bbbb 14College of Computer Science & Technology, BUPT第二節(jié) 文法n定義：所謂文法是用來(lái)定義語(yǔ)言的一個(gè)數(shù)學(xué)模型：所謂文法是用來(lái)定義

12、語(yǔ)言的一個(gè)數(shù)學(xué)模型n表示語(yǔ)言的方法：n若語(yǔ)言若語(yǔ)言L是有限集合，可用是有限集合，可用列舉法n若若L是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），是無(wú)限集合（集合中的每個(gè)元素有限長(zhǎng)度），用其他方法。用其他方法。n方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)方法一：文法產(chǎn)生系統(tǒng)，由定義的文法規(guī)則產(chǎn)生出語(yǔ)言的每個(gè)句子生出語(yǔ)言的每個(gè)句子n方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一方法二：機(jī)器識(shí)別系統(tǒng)：當(dāng)一個(gè)字符串能被一個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)個(gè)語(yǔ)言的識(shí)別系統(tǒng)接受，則這個(gè)字符串是該語(yǔ)言的一個(gè)句子，否則不屬于該語(yǔ)言。言的一個(gè)句子，否則不屬于該語(yǔ)言。15College of Computer Scien

13、ce & Technology, BUPT元語(yǔ)言元語(yǔ)言n定義定義：描述語(yǔ)言的語(yǔ)言描述語(yǔ)言的語(yǔ)言例如：各種各樣的程序設(shè)計(jì)語(yǔ)言例如：各種各樣的程序設(shè)計(jì)語(yǔ)言n當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要當(dāng)人們要解釋或討論程序設(shè)計(jì)語(yǔ)言本身時(shí)，又需要一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程一種語(yǔ)言，被討論的語(yǔ)言叫做對(duì)象語(yǔ)言，即某種程序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱為元語(yǔ)言序設(shè)計(jì)語(yǔ)言，討論對(duì)象語(yǔ)言的語(yǔ)言稱為元語(yǔ)言。16College of Computer Science & Technology, BUPTBNF（巴科斯范式）巴科斯范式） BNF范式通常被作為討論某種程序設(shè)計(jì)語(yǔ)言語(yǔ)法

14、的元語(yǔ)言n := 0|1|2|9 := “定義為”n := A|B|C|Z|a|b|z : = | | . n通過上述定義可知，所有以字母開頭的，由字母和數(shù)字組成的字符串都是標(biāo)識(shí)符。nBNF定義了一種語(yǔ)言，其中標(biāo)識(shí)符如上定義。nBNF描述它所定義的語(yǔ)言，為元語(yǔ)言。17College of Computer Science & Technology, BUPTn例如：漢語(yǔ)語(yǔ)法中定義了句子的結(jié)構(gòu)由主語(yǔ)、謂語(yǔ)、賓語(yǔ)組成。這里主謂賓只是描述了句子的結(jié)構(gòu)，并不是句子。而按照這種結(jié)構(gòu)組成的建立在漢字上的字符串就是句子。如他是學(xué)生。n文法是一種元語(yǔ)言，一種方法，根據(jù)文法產(chǎn)文法是一種元語(yǔ)言，一種方法，

15、根據(jù)文法產(chǎn)生出語(yǔ)言的句子。生出語(yǔ)言的句子。18College of Computer Science & Technology, BUPT三、Chomsky文法體系n例如：BNF := := := :=a|b|z|A|B|Z :=0|1|9將:= 改為表示可被代替用I, L, D分別表示標(biāo)識(shí)符、字母、數(shù)字;19College of Computer Science & Technology, BUPT則上述表達(dá)式可以表示為則上述表達(dá)式可以表示為 IL IIL IID La|b|.|z D0|1|.9這就是一個(gè)文法的生成式集合。這就是一個(gè)文法的生成式集合。20College of

16、 Computer Science & Technology, BUPTnChomsky文法體系中，任何一種文法必須包含有兩個(gè)不同的有限符號(hào)的集合，即非終結(jié)符集合N和終結(jié)符集合T。一個(gè)形式規(guī)則的有限集合P（生成式集合），一個(gè)起始符S。nP中的生成式是用來(lái)產(chǎn)生語(yǔ)言句子的規(guī)則，而句子則是僅由終結(jié)符組成的字符串。這些字符串必須從一個(gè)起始符S開始，不斷使用P中的生成式而導(dǎo)出來(lái)。n可見文法的核心是生成式的集合，它決定了語(yǔ)言中句子的產(chǎn)生。21College of Computer Science & Technology, BUPT文法的形式定義n文法G是一個(gè)四元組G=(N，T，P，S)，

17、 其中N 非終結(jié)符的有限集合T 終結(jié)符的有限集合 NT=P 形式為的生成式的有限集合。 且(NT)* N+ (NT)* (NT)*S 起始符 且S N。22College of Computer Science & Technology, BUPTn將上例用文法表示G=(N，T，P，S)N = I, L, DT = a, b, c,z, 0, 1, 9P = I, La, , D0, , D9S = I n文法是語(yǔ)言的產(chǎn)生系統(tǒng)，研究怎樣構(gòu)造文法能產(chǎn)生出符合要求的句子。23College of Computer Science & Technology, BUPT四推導(dǎo)與句型1、

18、直接推導(dǎo)設(shè)G =（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，則有A= 稱A直接推導(dǎo)出，或說是A的直接推導(dǎo)。24College of Computer Science & Technology, BUPTn設(shè)G = (N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、 =n，其中i直接推導(dǎo)出i+1 （0in）,則稱序列0=1=2=n是長(zhǎng)度為n的推導(dǎo)序列，而=0是長(zhǎng)度為0的推導(dǎo)序列。n對(duì)推導(dǎo)出記為 ，若推導(dǎo)序列長(zhǎng)度大于0，則記為 。n推導(dǎo)序列的每一步，都產(chǎn)生一個(gè)字符串，這些字符串一般稱為句型。2、推導(dǎo)序列*G G 25College of C

19、omputer Science & Technology, BUPT3、句型和句子n句型字符串字符串是文法是文法G的句型，當(dāng)且僅當(dāng)?shù)木湫停?dāng)且僅當(dāng)S ，且且（NT）*。n 句子是是G的句子，當(dāng)且僅當(dāng)?shù)木渥?，?dāng)且僅當(dāng)S ,且且T*。（。（是由是由終結(jié)符組成的字符串）終結(jié)符組成的字符串）例：例：I =L =a I =IL =LL =zL =zbn句型包含句子*G *G 26College of Computer Science & Technology, BUPT4文法產(chǎn)生的語(yǔ)言由文法由文法G產(chǎn)生的語(yǔ)言記為產(chǎn)生的語(yǔ)言記為L(zhǎng)(G)。 L(G) = |T*且且S 或：或： L(G)中的

20、一個(gè)字符串，必是由終結(jié)符中的一個(gè)字符串，必是由終結(jié)符組成的，并且是從起始符組成的，并且是從起始符S推導(dǎo)出來(lái)的。推導(dǎo)出來(lái)的。*G 27College of Computer Science & Technology, BUPT第三節(jié) Chomsky文法體系分類n文法文法 G = (N,T,P,S)； P: 其中其中 （NT）* N+（NT）* （NT）* 屬于屬于Chomsky文法體系文法體系n該體系對(duì)生成式的形式做了一些規(guī)定，分該體系對(duì)生成式的形式做了一些規(guī)定，分為四類，即為四類，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：無(wú)限制文法型文法：無(wú)限制文法對(duì)應(yīng)的語(yǔ)言：遞歸可枚

21、舉語(yǔ)言，與圖靈機(jī)等價(jià)。28College of Computer Science & Technology, BUPT1型文法n也稱上下文有關(guān)文法（也稱上下文有關(guān)文法（CSG：Context-sensitive Grammar)生成式的形式為生成式的形式為，其中其中 |，（NT）+， （NT）*N+（NT）*n對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（對(duì)應(yīng)的語(yǔ)言：上下文有關(guān)語(yǔ)言（CSL：Context-sensitive Language)n若不考慮若不考慮，與線性有界自動(dòng)機(jī)（與線性有界自動(dòng)機(jī)（LBA, Linear Bounded Automaton）等價(jià)。等價(jià)。29College of Comp

22、uter Science & Technology, BUPT2型文法n也稱上下文無(wú)關(guān)文法（也稱上下文無(wú)關(guān)文法（CFG：Context-free Grammar) A , AN, 且且 （NT）*n對(duì)應(yīng)的語(yǔ)言：上下文無(wú)關(guān)語(yǔ)言對(duì)應(yīng)的語(yǔ)言：上下文無(wú)關(guān)語(yǔ)言 （CFL： Context-free Language)。n對(duì) 應(yīng) 的 自 動(dòng) 機(jī) ： 下 推 自 動(dòng) 機(jī) （對(duì) 應(yīng) 的 自 動(dòng) 機(jī) ： 下 推 自 動(dòng) 機(jī) （ P D A ： Pushdown Automaton)。30College of Computer Science & Technology, BUPT3型文法也稱正則文

23、法也稱正則文法n右線性文法（右線性文法（Right-linear Grammar）：）：AB 或或 AA、BN, T*。n左線性文法（左線性文法（Left-linear Grammar）：）：AB或或 AA、BN, T*。n對(duì)應(yīng)的語(yǔ)言：正則語(yǔ)言對(duì)應(yīng)的語(yǔ)言：正則語(yǔ)言n對(duì) 應(yīng) 的 自 動(dòng) 機(jī) ： 有 限 自 動(dòng) 機(jī) （對(duì) 應(yīng) 的 自 動(dòng) 機(jī) ： 有 限 自 動(dòng) 機(jī) （ F i n i t e Automaton）。）。31College of Computer Science & Technology, BUPT例例1：G = (A,B,C, a,b,d, P, A) P: AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。 A=dA=AB =dB =daA=AB =ABB =dBB =daB =daaA=AB =CAAB =bAAB =bdAB =bdCAAB =bdbAAB =bdbdAB=bdbddB =bdbdda32College of Computer Science & Technology, BUPT例例2：G = (A,B,C, a,b,c, P, A) P: Aabc AaBbc BbbB