《形式语言与自动机》课件chap2-文法与语言.ppt
《《形式语言与自动机》课件chap2-文法与语言.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件chap2-文法与语言.ppt(35页珍藏版)》请在文库网上搜索。
1、12023/6/7School of Computer Science,BUPT第二章第二章 语言及文法语言及文法n主要内容主要内容:n定定义形式形式语言的言的术语n给出文法的定出文法的定义和文法的分和文法的分类n要求掌握:要求掌握:n语言和文法的形式定言和文法的形式定义nCHOMSKY文法体系的分文法体系的分类。22023/6/7School of Computer Science,BUPT第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些言的一些术语:n 字母表:字母表:字符的有限集合,字符的有限集合,记为T。n字符串:字符串:由字母表由字母表T中的字符构成的序中的字符构成的
2、序列称字母表列称字母表T上的字符串(句子)。上的字符串(句子)。n 常常记为u,v,w,x,y,z;n 常用常用a,b,c,d 标识单个字符。个字符。32023/6/7School of Computer Science,BUPT字字 母母 表表(Alphabet)概念概念 形式符号的集合形式符号的集合 记号号 常用常用 T、表示表示 举例例-英文字母表英文字母表 a,b,z,A,B,Z -英文英文标点符号表点符号表 ,;:.?!“”()-汉字表字表 ,自自,动,机机,-化学元素表化学元素表 H,He,Li,-T=a,n,y,42023/6/7School of Computer Scienc
3、e,BUPT字字 符符 串串(string)概念概念 字母表字母表 T 上的一个上的一个字符串字符串(简称称串串),或称),或称为 字字(word),),为 T 中字符构成的一个有限序列。中字符构成的一个有限序列。空串空串(empty string),用用 表示,不包含任何字符。表示,不包含任何字符。举例例 设 T=a,b ,则 ,a,ba,bbaba 等都是串等都是串 字符串字符串 w 的的长度度,记为 w ,是包含在是包含在 w 中字符的中字符的个数。个数。举例例 =0,bbaba =5 ai 表示含有表示含有i个个a的字符串的字符串 52023/6/7School of Computer
4、 Science,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 关关 于于 字字 符符 串串 的的 运运 算算62023/6/7School of Computer Science,BUPT 其它其它 如如 取取头字符字符,取尾部取尾部,子串匹配子串匹配 等等n 设1,2,3是是字字母母表表T上上的的字字符符串串,称称1是是字字符符串串12的的前前缀,2是是字字符符串串12的的
5、后后缀,且且2是是字符串字符串123的子串。的子串。n 空串是任何字符串的前空串是任何字符串的前缀,后,后缀及子串。及子串。n 例例:abc的前的前缀 a ab abc.后后缀 c bc abc.子串子串 a b c ab bc abc ,即一个字符串可以看作是多个字符串的即一个字符串可以看作是多个字符串的连接。接。关关 于于 字字 符符 串串 的的 运运 算算72023/6/7School of Computer Science,BUPTn 字符串字符串的逆用的逆用 表示。表示。是是字符串字符串的倒置。的倒置。=b1b2bn =bnbn-1b2b1n 空串空串的逆的逆还是是82023/6/7
6、School of Computer Science,BUPT字字 母母 表表 的的 幂 运运 算算 幂运算运算 设 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*92023/6/7School of Computer Science,BUPT闭包的物理意包的物理意义 T的星号的星号闭包包T*:字母表T上的所有字符串和空串的集合。T的正的正闭包包T+:字母表T上的所有
7、字符串构成的集合。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,102023/6/7School of Computer Science,BUPT语 言(Languages)概念概念 设设 T 为字母表,则任何集合为字母表,则任何集合 L T*是是字字母表母表T上的上的一个语言(一个语言(language)举例举例 -英文单词集英文单词集 ,English,words,-C 语言程序集语言程序集 字母表?字母表?-汉语成语集汉语成语集 ,马到成功马到成功,-化学分子式
8、集化学分子式集 ,H2O,NaCl,-any,112023/6/7School of Computer Science,BUPT语 言(Languages)举例举例:设T=a,b 则 L1 =anbn|n1 L3=bk|k 是是质数数 L2 =只有一个空句子的只有一个空句子的语言言 L4=空空语言言 均均为字母表字母表T上的上的语言。言。由由语言的定言的定义知知语言是集合,言是集合,对于集合的运算可于集合的运算可应用于用于对于于语言的言的计算。如并,交,算。如并,交,补,差。,差。122023/6/7School of Computer Science,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,babb L2 L1=aaab,aaba,bbab,bbban L1 L2 L2 L1 语言的言的积不可交不可交换。132023/6/7School of Computer Science,BUPT语言的基本运算 语言的幂:语言的幂:语言的言的幂可可归纳定定义如下如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中,上例中,L12
10、=abab,abba,baab,baba L22=aaaa,aabb,bbaa,bbbb 142023/6/7School of Computer Science,BUPT第二节 文法n定义:所:所谓文法是用来定文法是用来定义语言的一个数学模型言的一个数学模型n表示语言的方法:n若若语言言L是有限集合,可用是有限集合,可用列举法n若若L是是无无限限集集合合(集集合合中中的的每每个个元元素素有有限限长度度),用其他方法。用其他方法。n方方法法一一:文文法法产生生系系统,由由定定义的的文文法法规则产生出生出语言的每个句子言的每个句子n方方法法二二:机机器器识别系系统:当当一一个个字字符符串串能能被
11、被一一个个语言言的的识别系系统接接受受,则这个个字字符符串串是是该语言的一个句子,否言的一个句子,否则不属于不属于该语言。言。152023/6/7School of Computer Science,BUPT元语言元语言n定定义:描述描述语言的言的语言言例如:各种各例如:各种各样的程序的程序设计语言言n当当人人们要要解解释或或讨论程程序序设计语言言本本身身时,又又需需要要一一种种语言言,被被讨论的的语言言叫叫做做对象象语言言,即即某某种种程程序序设计语言,言,讨论对象象语言的言的语言称言称为元元语言言。162023/6/7School of Computer Science,BUPTBNF(巴
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 chap2 文法 语言