形式語言與自動機課件——語言及文法

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

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

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

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

5、x（ y z ）- x x x - x y x + y 關關 于于 字字 符符 串串 的的 運運 算算6College of Computer Science & Technology, BUPT 其它其它 如如 取頭字符取頭字符，取尾部取尾部，子串匹配子串匹配 等等n 設設1, 2, 3是字母表是字母表T上的字符串，稱上的字符串，稱1是字符是字符串串12的前綴，的前綴，2是字符串是字符串12的后綴，且的后綴，且2是字符串是字符串123的子串。的子串。 n 空串是任何字符串的前綴，后綴及子串?？沾侨魏巫址那熬Y，后綴及子串。n 例例：abc的前綴的前綴 a ab abc . 后綴后

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

7、運算 設設 T 為字母表，為字母表，n 為任意自然數(shù)，為任意自然數(shù)， 定義（定義（1） T0 = （2）設）設 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的星號閉包的星號閉包T*：字母表T上的所有字符串和空串的集合。 T的正閉包的正閉包T+：字母表T上的所有字符串構成的集合。T*

8、= T+ 舉例舉例 設設 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語 言 （Languages） 概念概念 設設 T 為字母表，則任何集合為字母表，則任何集合 L T* 是是字母字母表表T上的上的一個語言（一個語言（language） 舉例舉例 - 英文單詞集英文單詞集 , English, , words , - C 語言程序集語言

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

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

11、 語言的積不可交換。語言的積不可交換。13College of Computer Science & Technology, BUPT語言的基本運算 語言的冪：語言的冪：語言的冪可歸納定義如下語言的冪可歸納定義如下: 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定義：所謂文法是用來定義語言的一個數(shù)學模型：所謂文法是用來定義語言的一

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

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

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

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

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

17、 非終結符的有限集合T 終結符的有限集合 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文法是語言的產生系統(tǒng)，研究怎樣構造文法能產生出符合要求的句子。23College of Computer Science & Technology, BUPT四推導與句型1、直接推導

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

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

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

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

22、 Science & Technology, BUPT2型文法n也稱上下文無關文法（也稱上下文無關文法（CFG：Context-free Grammar) A , AN, 且且 （NT）*n對應的語言：上下文無關語言對應的語言：上下文無關語言 （CFL： Context-free Language)。n對 應 的 自 動 機 ： 下 推 自 動 機 （對 應 的 自 動 機 ： 下 推 自 動 機 （ 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對應的語言：正則語言對應的語言：正則語言n對 應 的 自 動 機 ： 有 限 自 動 機 （對 應 的 自 動 機 ： 有 限 自 動 機 （ 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