五莲建设监理有限公司网站,乱起封神是那个网站开发的,如何进行网络营销服务创新,学生管理系统wordpress《计算机数学基础课件》由会员分享#xff0c;可在线阅读#xff0c;更多相关《计算机数学基础课件(37页珍藏版)》请在人人文库网上搜索。1、计算机科学的数学基础,第一章#xff1a;语言与正规语言,1.1 符号、符号串及其运算,符号和符号串在形式语言中是非常重要的基本概念…《计算机数学基础课件》由会员分享可在线阅读更多相关《计算机数学基础课件(37页珍藏版)》请在人人文库网上搜索。1、计算机科学的数学基础,第一章语言与正规语言,1.1 符号、符号串及其运算,符号和符号串在形式语言中是非常重要的基本概念。,在计算机科学的发展中符号主义一直占据着非常重要的位置。,语言的基础是字母表。,王雷版权所有,1.1 符号、符号串及其运算,字母表一个非空的有限集合称为字母表通常用或者大写的西文字母表示。字母表中的元素称作为字母或符号一般用小写字母、数字等表示。,符号串一个符号串是由字母表中的字母组成的一个有限序列。,符号串的长度符号串所包含符号的个数称为符号串的长度。符号串w的长度记为|w|。,空串长度为0的符号串称为空串用表示。,王雷版权所有,1.1 符号、符号串及其运。2、算,符号串的联结联结是符号串的基本运算。两个符号串X和Y的联结记为XY就是把Y跟随在X的后面形成的符号串。,例1.1设 1, 2是一个字母表。设X 11、Y 22分别是上的两个符号串。则 XY 1122是X、Y两个符号串的联结XY是上的一符号串。 YX 2211是Y、X两个符号串的联结YX也是上的一符号串。,一般来说符号串的联结不满足交换律。显然符号串的联结是满足结合律的即有(XY)Z X(YZ)。在例1.1中显然有XYYX(XY)X X(YX) 112211。,王雷版权所有,1.1 符号、符号串及其运算,由于是不含符号的符号串(空串)。3、所以对任意符号串X都有X X X。由此我们可以认为是符号串联结运算的单位元。,符号串的方幂设X是符号串把X自身联结n次后得到的符号串Z即Z XXXX Xn称为X的方幂。我们约定X0 。这个定义可以递归地表示为,A,B,王雷版权所有,1.1 符号、符号串及其运算,符号串的子串、前缀和后缀 符号串V是符号串W的子串当且仅当存在符号串X和Y使得W XVY。这里X和Y都可能是空串。,集合的联结设A和B都是符号串的集合定以集合A和B的联结为 AB XY | XA且YB 即集合A和B的联结是集合A中的符号串和集合B中的符号串的联结所构成的集合。,A。4、,B,王雷版权所有,1.1 符号、符号串及其运算,集合的方幂设A是符号串的集合把A自身联结n次后得到的新的集合An即An AAA称为集合A的方幂。 我们约定A0 。这个定义可以递归地表示为,王雷版权所有,1.1 符号、符号串及其运算,集合的闭包和正闭包设A是符号串的集合用A*表示A的所有的有限次方幂的并集则称A*为集合A上的闭包即,注意闭包A*与正闭包A的差别在于是否包含空串。在闭包A*中去掉空串后就成为正闭包A。A* 具有可数无穷多的符号串。,A* A0A1A2An 而称A A1A2An 为A上的正闭包显然,有 A* A0 A A 。5、 A*A AA*。,语言令为一个字母表。若L *则L是字母表上的一个语言。 即L为一个由字母表上的字符串所构成的集合。,王雷版权所有,1.2 文法与语言的形式定义,语言都是用文法来描述的。 一个文法实际上是一组有限的规则式。,非终结符(一种过渡性符号)也是一种符号但不是字母表中的符号。我们将它记为V。,终结符是一个语言的字母表中的符号。我们将它记为T。,对于一个形式语言L设T和V分别是它的终结符集和非终结符集显然有L T*且TV 。,王雷版权所有,1. 2. 1 文法的形式化定义,王雷版权所有,1. 2. 1 文法的形式化定义,王雷版权所有,1. 2. 1 文法的形。6、式化定义,王雷版权所有,1. 2. 2 推导的形式化定义,王雷版权所有,1. 2. 2 推导的形式化定义,王雷版权所有,1. 2. 2 推导的形式化定义,规范句型、短语、直接短语和句柄,定义1. 5给定一个文法G (V, T, P, S)如果符号串x是从文法G的开始符号S推导出来的即S *x则称x是文法G的句型。如果符号串x是仅由终结符组成的句型即S*x且xT*则称x是文法G的句子。 由规范推导所得到的句型就称之为规范句型。,王雷版权所有,1. 2. 2 推导的形式化定义,规范句型、短语、直接短语和句柄,定义1. 6 设GS是一文法x w是一句型 如果S*A且A * 。7、w 则称w是句型x的一个相对于非终结符A的短语 如果S*A且Aw 则称w是句型x的一个相对于非终结符的直接短语(或简单短语) 如果w是一个句型x的最左直接短语称w为句型x的句柄。,王雷版权所有,1.2.3 语言的形式化定义,王雷版权所有,1.2.3 语言的形式化定义,王雷版权所有,1.2.3 语言的形式化定义,王雷版权所有,1.2.4 语法树,王雷版权所有,1.2.4 语法树,定义1.9 如果一个文法存在某个句子对应两棵以上的不同的语法树或有两个以上的不同的最左(右)推导则称该文法是二义性文法(程序设计语言不能有二义性 )。,定义1.10 如果一个语言L的任何文法都是二义性文法则。8、称该语言L是二义性语言。 在理论上已经证明了存在着这种二义性的语言。 文法的二义性与语言的二义性是两个不同的概念。,A,B,王雷版权所有,1.2.5 文法和语言的类型,王雷版权所有,诺姆乔姆斯基(Noam Chomsky, 1928-)美国语言学家转换-生成语法的创始人。1928年12月7日出生于美国宾夕法尼亚州的费城。1947年在哈里斯的影响下他开始研究语言学。1951年在宾夕法尼亚大学完成硕士论文现代希伯莱语语素音位学1955年在该校完成博士论文转换分析获得博士学位。从1955年秋天开始他一直在麻省理工学院工作曾任该校语言学与哲学系主任并任该校认知科学研究中心主任为语言。9、学界培养了一批有素养的学者。,1.2.5 文法和语言的类型,王雷版权所有,1.2.5 文法和语言的类型,王雷版权所有,1.2.5 文法和语言的类型,王雷版权所有,1.2.5 文法和语言的类型,王雷版权所有,1.2.5 文法和语言的类型,王雷版权所有,1.3 正规表达式(正规式 ),王雷版权所有,1.3 正规表达式(正规式 ),王雷版权所有,1.3 正规表达式(正规式 ),王雷版权所有,1.3 正规表达式(正规式 ),王雷版权所有,1.3 正规表达式(正规式 ),正规表达式运算符的优先级顺序,王雷版权所有,1.4 正规文法与正规式,一个正规语言可以由正规文法定义也可由正规式定义对任意一个正规文法存在一个定义同一个语言的正规式反之对于每一个正规式存在一个生成同一语言的正规文法。,正规表达式和正规文法 之间是可以互相转换的。,王雷版权所有,1.4 正规文法与正规式,正规表达式转换成正规文法,王雷版权所有,1.4 正规文法与正规式,将正规文法转换成正规式,王雷版权所有,1.4 正规文法与正规式,将正规文法转换成正规式,王雷版权所有,1.4 正规文法与正规式,将正规文法转换成正规式,王雷版权所有,Thank You !,王雷 湘潭大学信息工程学院 2012版权所有。
