《形式语言与自动机——语言及文法》由会员分享，可在线阅读，更多相关《形式语言与自动机——语言及文法（47页珍藏版）》请在金锄头文库上搜索。
1、College of Computer Science & Technology, BUPT,第二章 语言及文法,主要内容： 定义形式语言的术语 给出文法的定义和文法的分类 要求掌握： 语言和文法的形式定义 文法如何设计 CHOMSKY文法体系的分类。,College of Computer Science & Technology, BUPT,引言,复习： 什么是形式语言？什么是文法？什么是自动机？ 形式语言的定义方式？ 研究形式语言与自动机的意义？ 问题的提出？本章关注 语言与文法 如何描述（产生）左右括号匹配的语言？ 如何描述（产生）数学表达式？,College of Computer
2、Science & Technology, BUPT,引言,知识点： 形式语言所研究的问题：产生语言，根据语言中的基本句子和其它句子的形成“规则”，得到（产生）语言所包含的所有句子。,College of Computer Science & Technology, BUPT,第一节 语言的定义与运算,一、语言的一些术语：字母表： 字符的有限集合，记为T。 字符串： 由字母表T中的字符构成的序列称字母表T上的字符串（句子）。常记为u,v,w,x,y,z；常用a,b,c,d 标识单个字符。,College of Computer Science & Technology, BUPT,字 母 表
3、（Alphabet）,概念 形式符号的集合记号 常用 T、 表示举例英文字母表 a, b, , z, A, B , , Z 英文标点符号表 , ; : . ? ! “ ” ( ) 汉字表 , 自, , 动 , , 机, 化学元素表 H, He, Li, , T = a, n, y, 任,意 ,College of Computer Science & Technology, BUPT,字 符 串 （string）,概念 字母表 T 上的一个字符串（简称串），或称为字（word），为 T 中字符构成的一个有限序列。空串（empty string）, 用 表示，不包含任何字符。举例 设 T = a
4、, b ，则 , a, ba, bbaba 等都是串字符串 w 的长度，记为 w ，是包含在 w 中字符的个数举例 = 0， bbaba = 5ai 表示含有i个a的字符串,College 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 x（ y z ） x x x x y x+y,关 于 字 符 串 的 运 算,College of Computer Science
5、 & Technology, BUPT,其它 如 取头字符，取尾部，子串匹配 等设1, 2, 3是字母表T上的字符串，称： 1是字符串12的前缀， 2是字符串12的后缀， 2是字符串123的子串。 空串是任何字符串的前缀，后缀及子串。例：abc的前缀 a ab abc . 后缀 c bc abc . 子串 a b c ab bc abc , 即一个字符串可以看作是多个字符串的连接。,关 于 字 符 串 的 运 算,College of Computer Science & Technology, BUPT,字符串的逆用 表示。 是字符串的倒置。 = b1b2bn= bnbn-1b2b1空串的逆
6、还是,College of Computer Science & Technology, BUPT,字 母 表 的 幂 运 算,幂运算 Tn 用来表示 该字母表长度为n的所有串的集合。设 T 为字母表，n 为任意自然数，定义（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* ,College of Computer Science & Technology, BUPT,闭包的物理意义,T的星号闭包T*：字母表T上的所有字符串和空串
7、的集合。T的正闭包T+：字母表T上的所有字符串构成的集合。T*= 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， ,College of Computer Science & Technology, BUPT,概念 设 T 为字母表，则任何集合 L T* 是字母表T上的一个语言（language）。隐含的概念：如何表述子集的“特性和规则”，举例 - 左右括号的匹配。英文单词集 , English, , words , C 语言程序集
8、字母表？汉语成语集 , 马到成功, 化学分子式集 , H2O, , NaCl , any, 任意 ,语 言 （Languages）,College of Computer Science & Technology, BUPT,语 言 （Languages）,举例：设T = a，b 则 L1 = anbn | n1 L3 = bk | k 是质数L2 = 只有一个空句子的语言 L4 = = 空语言 均为字母表T上的语言。 由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。,College of Computer Science & Technology, BUPT
9、,语言的基本运算,语言的积：两个语言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, babbL2 L1 =aaab, aaba, bbab, bbbaL1 L2 L2 L1 语言的积不可交换。,College of Computer Science & Technology, BUPT,语言的基本运算,语言的幂：语言的幂可归纳定义如下: L0 = Ln = L Ln-1
10、= Ln-1 L n 1上例中， L12 =abab, abba, baab, babaL22 =aaaa, aabb, bbaa, bbbb,College of Computer Science & Technology, BUPT,语言举例,例1：括号匹配的语言及产生 该语言指所有左右括号相匹配的字符串 如何“产生”这个语言？规则？ 递归定义提供了集合的定义方式。构造规律。 基础：定义该集合的最基本的元素，“（）” 递归：若S是合法串，则：（S）是合法串；SS 是合法串；,College of Computer Science & Technology, BUPT,语言举例,例2：程序设
11、计语言中算数表达式的语言运算符A ：+、-、*、/ 利用递归定义方式。重点是构造规律。 基础：单个变量是最基本的串，i, 递归：若S是合法串，则：SAS 是合法串；（ S）是合法串；,College of Computer Science & Technology, BUPT,语言举例,例3：标识符语言及产生 该语言指所有字母开头后接字母或数字的字符串 如何“产生”这个语言？规则？ 递归定义提供了集合的定义方式。构造规律。 基础：单个字母是最基本的元素， 递归：若S是合法串，则：SL 是合法串；SD 是合法串； L：字母；D：数字。,College of Computer Science &
12、Technology, BUPT,第二节 文法,本节提纲 文法的作用 文法的形式定义 推导与句型 文法产生语言,College of Computer Science & Technology, BUPT,2.1 文法的作用,定义：所谓文法是用来定义语言的一个数学模型 表示语言的方法： 若语言L是有限集合，可用列举法 若L是无限集合（集合中的每个元素有限长度），用其他方法。 方法一：文法产生系统，由定义的文法规则产生出语言的每个句子 方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语言的一个句子，否则不属于该语言。,College of Computer Scie
13、nce & Technology, BUPT,2.1文法的作用-元语言,元语言定义：描述语言的语言例如：各种各样的程序设计语言 当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言。,College of Computer Science & Technology, BUPT,BNF（巴科斯范式）,BNF范式通常被作为讨论某种程序设计语言语法的元语言:= 0|1|2|9 := “定义为”:= A|B|C|Z|a|b|z : = | | . 通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。 BNF
14、定义了一种语言，其中标识符如上定义。 BNF描述它所定义的语言，为元语言。,College of Computer Science & Technology, BUPT,例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如: 他是学生。,College of Computer Science & Technology, BUPT,文法是一种元语言，一种定义方法。 根据文法产生出语言的句子。,College of Computer Science & Technology, BUPT,2.1文法元
15、语言,例如： BNF :=:=:= :=a|b|z|A|B|Z:=0|1|9将:= 改为表示可被代替 用I, L, D分别表示标识符、字母、数字;,College of Computer Science & Technology, BUPT,2.1 文法-元语言,则上述表达式可以表示为 ILIILIIDLa|b|.|zD0|1|.9 这就是一个文法的生成式集合。,College of Computer Science & Technology, BUPT,2.2 文法的形式定义,Chomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。 P中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而推导出来。 可见文法的核心是生成式的集合，它决定了语言中句子的产生。,
