计算机数学基础优秀PPT.ppt

《计算机数学基础优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机数学基础优秀PPT.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机数学基础现在学习的是第1页，共37页1.1 符号、符号串及其运算符号、符号串及其运算字母表：字母表：一个非空的有限集合称为字母表，通常用或者大写的西文字母表示。字母表中的元素称作为字母或符号，一般用小写字母、数字等表示。符号串：符号串：一个符号串是由字母表中的字母组成的一个有限序列。符号串的长度：符号串的长度：符号串所包含符号的个数称为符号串的长度。符号串w的长度记为|w|。空串：空串：长度为0的符号串称为空串，用表示。王雷版权所有现在学习的是第2页，共37页1.1 符号、符号串及其运算符号、符号串及其运算符号串的联结符号串的联结：联结是符号串的基本运算。两个符号串X和Y的联结，记为XY

2、，就是把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。王雷版权所有现在学习的是第3页，共37页1.1 符号、符号串及其运算符号、符号串及其运算由于是不含符号的符号串(空串)，所以对任意符号串X都有，X=X =X。由此我们可以认为是符号串联结运算的

3、单位元。符号串的方幂符号串的方幂：设X是符号串，把X自身联结n次后，得到的符号串Z，即Z=XXXX=Xn，称为X的方幂。我们约定X0 =。这个定义可以递归地表示为：王雷版权所有现在学习的是第4页，共37页1.1 符号、符号串及其运算符号、符号串及其运算符号串的子串、前缀和符号串的子串、前缀和后缀：后缀：符号串V是符号串W的子串，当且仅当存在符号串X和Y，使得W=XVY。这里，X和Y都可能是空串。集合的联结：集合的联结：设A和B都是符号串的集合，定以集合A和B的联结为：AB=XY|XA且YB，即集合A和B的联结是集合A中的符号串和集合B中的符号串的联结所构成的集合。王雷版权所有现在学习的是第5页

4、，共37页1.1 符号、符号串及其运算符号、符号串及其运算集合的方幂集合的方幂：设A是符号串的集合，把A自身联结n次后，得到的新的集合An，即An=AAA，称为集合A的方幂。我们约定A0=。这个定义可以递归地表示为：王雷版权所有现在学习的是第6页，共37页1.1 符号、符号串及其运算符号、符号串及其运算集合的闭包和正闭包集合的闭包和正闭包：设A是符号串的集合，用A*表示A的所有的有限次方幂的并集，则称A*为集合A上的闭包，即：注意：闭包A*与正闭包A+的差别在于是否包含空串。在闭包A*中去掉空串后就成为正闭包A+。A*具有可数无穷多的符号串。A*=A0A1A2An而称A+=A1A2An 为A上

5、的正闭包，显然,有A*=A0 A+，A+=A*A=AA*。语言：语言：令为一个字母表。若L *，则L是字母表上的一个语言。即：L为一个由字母表上的字符串所构成的集合。王雷版权所有现在学习的是第7页，共37页1.2 文法与语言的形式定义文法与语言的形式定义语言都是用文法来描述的。一个文法实际上是一组有限的规则式。非终结符（非终结符（一种过渡性符号一种过渡性符号）：也是一种符号，但不是字母表中的符号。我们将它记为V。终结符终结符：是一个语言的字母表中的符号。我们将它记为T。对于一个形式语言L，设T和V分别是它的终结符集和非终结符集，显然有L T*，且TV =。王雷版权所有现在学习的是第8页，共37

6、页1.2.1 文法的形式化定义文法的形式化定义定义定义1.1：一条产生式是一个有序对(,),通常可写作如下形式 =或 其中：V+，V*，V=VT。称为产生式的左部，称为产生式的右部。注意：V+说明是一个非终结符且，即产生式的左部不允许是空串。V*说明产生式的右部是这样的一个符号串，它可以含有终结符，也可以含有非终结符，同时还可以为空串。王雷版权所有现在学习的是第9页，共37页1.2.1 文法的形式化定义文法的形式化定义定义定义1.2：文法G定义为一个四元组G=(V，T，P，S),其中：1、V是一个非空的有穷集合，称为非终结符集。2、T是一个非空的有穷集合，称为终结符集，且VT =。3、P是一个

7、非空的有穷的产生式的集合。4、SV，称为文法的开始符号，S至少要在P中的一条产生式中作为左部出现。王雷版权所有现在学习的是第10页，共37页1.2.1 文法的形式化定义文法的形式化定义例例1.2 设文法G=(A,E，a，P，A)，其中P=Aa，AaE，EaA。在许多的文法中，有多条产生式的左部相同，可以将左部相同的产生式写成合并的产生式形式。在此例文法G中，P中的前两个产生式的左部相同，都是A，可以合并为A a|aE，这样一来，P=A a|aE，EaA。在许多情况下，只需要将文法的产生式写出就可以表明该文法了。约定：第一条产生式的左部是文法的开始符 王雷版权所有现在学习的是第11页，共37页1

8、.2.2 推导的形式化定义推导的形式化定义定义定义1.3：给定一个文法G=(V,T,P,S)，如果是G中的一条产生式，和是V*中的任意符号，若存在符号串x,y满足：x=，y=，则称x使用了产生式直接产生了y，或者称y是x的直接推导，或者称y可以直接归约到x，记作x y。例：令x=aAb，y=acb，=a，=b，则y是x的直接推导，即：aAb acb，所使用的产生式为Ac。王雷版权所有现在学习的是第12页，共37页1.2.2 推导的形式化定义推导的形式化定义定义定义1.4：给定一个文法G=(V,T,P,S)，设x，yV*，如果：1、存在如下的直接推导序列：x=w0 w1 w2 wn=y(n0)则

9、称x推导出(产生)y，推导长度为n，或者称为y归约到x，记作x n y。2、我们用x+y表示存在n0且x n y；用x*y表示有x+y或者x=y。最左最左(右右)推导推导：如果在推导的每一步x y，都是对x中的最左(右)边的非终结符选用产生式进行替换，则这种推导称为最左(右)推导。最右推导也称为规规范推导范推导。王雷版权所有现在学习的是第13页，共37页1.2.2 推导的形式化定义推导的形式化定义规范句型、规范句型、短语短语、直直接短语接短语和句柄句柄定义定义1.5：给定一个文法G=(V,T,P,S)，如果符号串x是从文法G的开始符号S推导出来的，即S*x，则称x是文法G的句型。如果符号串x是

10、仅由终结符组成的句型，即S*x且xT*，则称x是文法G的句子。由规范推导所得到的句型就称之为规范句型规范句型。王雷版权所有现在学习的是第14页，共37页1.2.2 推导的形式化定义推导的形式化定义规范句型、规范句型、短语短语、直直接短语接短语和句柄句柄定义定义1.6 设GS是一文法，x=w是一句型，如果：S*A且A*w则称w是句型x的一个相对于非终结符A的短语；如果：S*A且Aw则称w是句型x的一个相对于非终结符的直接短语(或简单短语)；如果w是一个句型x的最左直接短语，称w为句型x的句柄。王雷版权所有现在学习的是第15页，共37页1.2.3 语言的形式化定义语言的形式化定义定义定义1.7：给

11、定一个文法G=(V,T,P,S)，由G所生成的语言记作L(G)，令L(G)=x|S+x且xT*，其中x称为语言L(G)的句子。即：L(G)是一个由从文法G的开始符号S所推导出来的所有句子所构成的集合。例例1.3 给定文法GS：S aSb|ab 由该文法生成的任何一个句子都是：先使用产生式SaSb若干次得到：S aSb aaSbb an-1S bn-1，即S+an-1S bn-1；再使用产生式S ab一次得到：S+an-1S bn-1 anbn。不难对推导的步数用数学归纳法证明该文法推导的所有符号串都是anbn的形式。另一方面，我们也不难对符号串的长度用数学归纳法证明，对任何形式为anbn，n1

12、，的符号串，一定可以用文法GS推导出来，即存在推导S+anbn。所以，L(GS)=anbn|n1。王雷版权所有现在学习的是第16页，共37页1.2.3 语言的形式化定义语言的形式化定义例例1.4 设文法GV：V aVb，Vb bW，abW c。求文法GV所生成的语言。解：V是文法的开始符。继续多次使用该产生式，得到的推导结果是：anVbn，n1。在anVbn中，为了消除非终结符V，必须使用产生式VbbW，得到推导结果是：anbWbn-1=an-1abWbn-1，n1。只有使用产生式abWc，才能消除非终结符W，最终得到推导结果：an-1cbn-1，n1。另一方面，不难证明，对任何形式为ancb

13、n，n0的符号串都可以用文法GV推导出来。因此，文法GV生成的语言为：L(GV)=an-1cbn-1|n1=ancbn|n0。王雷版权所有现在学习的是第17页，共37页1.2.3 语言的形式化定义语言的形式化定义例例1.5 文法GA：AaR，Aab，RAb所生成的语言L(GA)=anbn|n1。(留做课后习题)。从上面可以看出，尽管文法GA与例1.7中的文法GS是两个不同的文法，但是所生成的语言是相同，都是anbn|n 1。定义定义1.8 给定任意两个文法G1、G2，如果它们所生成语言相同，即：L(G1)=L(G2)，则称文法G1与G2是等价的。王雷版权所有现在学习的是第18页，共37页1.2

14、.4 语法树语法树语法树是句型推导过程的图形表示。例如，设句子bd0的最右推导或规范推导为：0 0 d0 d0 bd0王雷版权所有bd0图图1.2 句子句子bd0的语法树的语法树现在学习的是第19页，共37页1.2.4 语法树语法树定义定义1.9 如果一个文法存在某个句子对应两棵以上的不同的语法树，或有两个以上的不同的最左(右)推导，则称该文法是二义性文二义性文法（程序设计语言不能有法（程序设计语言不能有二义性二义性）。定义定义1.10 如果一个语言L的任何文法都是二义性文法，则称该语言L是二义性语言。在理论上已经证明了，存在着这种二义性的语言。文法的二义性与语言的二义性是两个不同的概念。王雷

15、版权所有现在学习的是第20页，共37页1.2.5 文法和语言的类型文法和语言的类型Chomsky于1956年把文法分成四种类型，即：0型文法、1型文法、2型文法和3型文法。这种文法的分类称作Chomsky分类。文法所生成的语言，根据四种类型文法，也分为四种，即：0型语言、1型语言、2型语言和3型语言。Chomsky建立的形式语言理论对计算机科学的发展规律有着深刻的影响，特别是对计算机程序设计语言的设计、编译方法和计算复杂性等方面具有更大的作用。王雷版权所有诺姆诺姆乔姆斯基（乔姆斯基（Noam Chomsky,1928-），美国），美国语言学语言学家，转换家，转换-生生成语法的创始人。成语法的创

16、始人。1928年年12月月7日出生于美国日出生于美国宾夕法尼亚州宾夕法尼亚州的的费城费城。1947年，在年，在哈里斯哈里斯的影响下他开始研究语言学。的影响下他开始研究语言学。1951年在宾夕法尼亚大年在宾夕法尼亚大学完成硕士论文学完成硕士论文现代希伯莱语语素音位学现代希伯莱语语素音位学，1955年在该校完成博年在该校完成博士论文士论文转换分析转换分析，获得博士学位。从，获得博士学位。从1955年秋天开始，他一直在年秋天开始，他一直在麻省麻省理工学院理工学院工作，曾任该校语言学与哲学系主任，并任该校认知科学研究中工作，曾任该校语言学与哲学系主任，并任该校认知科学研究中心主任，为语言学界培养了一批

17、有素养的学者。心主任，为语言学界培养了一批有素养的学者。现在学习的是第21页，共37页1.2.5 文法和语言的类型文法和语言的类型定义定义1.11 设文法G=(V,T,P,S)，如果，对于P，满足(VT)+且中至少含有一个非终结符，(VT)*，则G称为0型文法（或短语结构文法，简记为PSG)或者无约束文法(Unrestricted Grammar)。0型文法能确保产生式的左部不为空。由0型文法所生成的语言称为0型语言或短语结构语言（简记为PSL）。0型文法的能力与图灵机（Turing Machine）相当。王雷版权所有现在学习的是第22页，共37页1.2.5 文法和语言的类型文法和语言的类型定

18、义定义1.12 设文法G=(V,T,P,S)，如果对于P，满足|(除S外)，则文法G称为1型文法或上下文有关文法，简记为CSG。1型文法的产生式的形式也被描述为：1A212，其中：1、2、(VT)+，AV。它更能体现“上下文有关”这一含义，因为，只有A出现在1和2之间（1为A的上文，2为A的下文），才允许用来取代A。1型文法所产生的语言称作1型语言或上下文有关语言(简记为CSL)。王雷版权所有现在学习的是第23页，共37页1.2.5 文法和语言的类型文法和语言的类型定义定义1.13 设文法G=(V,T,P,S)，如果，对于P，满足V，(VT)*，则称G为2型文法或上下文无关文法，简记为CFG。

19、上下文无关文法取名为“上下文无关”的原因就是因为字符 总可以被字串 自由替换，而无需考虑字符 出现的上下文。2型文法所产生的语言称作2型语言或上下文无关语言(简记为CFL)。一个简单的上下文无关文法的例子是：S-aSb|。由于这个文法的产生式的左边都是单个的非终结符S，右边是由终结符或非终结符构成的符号串aSb和，因此符合上下文无关语法产生式的要求。该文法产生的语言为 anbn:n 0。王雷版权所有现在学习的是第24页，共37页1.2.5 文法和语言的类型文法和语言的类型定义定义1.14：设文法G=(V,T,P,S)，如果P中的每一条产生式都是AaB或Aa形式，其中：A、BV，aT，则称G为3

20、型文法或正规文法,简记为RG。3型文法所产生的语言称作3型语言或正规语言(简记为RL)。3型语言与有限自动机等价，即有限自动机恰能识别3型语言。0型语言1型语言2型语言3型语言图1.4 形式语言的Chomsky层级在忽略句子的情况下，由Chomsky分类定义可知，任何3型语言都是2型语言，任何2型语言都是1型语言，任何1型语言都是0型语言。王雷版权所有现在学习的是第25页，共37页1.2.5 文法和语言的类型文法和语言的类型王雷版权所有0型语言1型语言2型语言3型语言图图1.4 形式语言的形式语言的Chomsky层级层级现在学习的是第26页，共37页1.3 正规表达式（正规式正规表达式（正规式

21、）正规式是按照一组定义规则，由较简单的正规式构成的，每个正规式e表示一个语言L(e)（正规集合）。定义定义1.15 字母表上的正规表达式和正规集递归定义如下：1、任意a，a是上的一个正规表达式，它所表示的正规集为a。2、空串是上的一个正规表达式，它所表示的正规集为。3、符号是上的一个正规表达式，它所表示的正规集为。4、设e1与e2都是上的正规表达式，它们所表示的正规集分别为L(e1)与L(e2)，则（1）e1+e2也是正规表达式，它所表示的正规集为 L(e1+e2)=L(e1)L(e2)（2）e1e2也是正规表达式，它所表示的正规集为 L(e1e2)=L(e1)L(e2)（3）(e1)*也是正

22、规表达式，它所表示的正规集为 L(e1)*)=(L(e1)*王雷版权所有现在学习的是第27页，共37页1.3 正规表达式（正规式正规表达式（正规式）例例1.7 令=a,b，下面表列出了上的一些正规表达和相应的正规集：王雷版权所有正规表达式 正规集 a+ba,ba*,a,aa,aaa,aaaa,aa*a,aa,aaa,aaaa,(a+b)(a+b)aa,ab,ba,bb(a+b)*,a,b,aa,ab,ba,bb,即所有含a和b的符号串(aa+ab+ba+bb)*空串或任何长度为偶数的a,b串(a+b)(a+b)(a+b)*)任何长度大于等于2的a,b串 现在学习的是第28页，共37页1.3 正

23、规表达式（正规式正规表达式（正规式）正规式的代数性质王雷版权所有公理 说明 r+s=s+r 运算+是可交换的 r+(s+t)=(r+s)+t 运算+是可结合的(rs)t=r(st)联结运算是可结合的 r(s+t)=rs+rt，(s+t)r=sr+tr 联结运算对+运算符是可分配的 r=r，r=r 对于联结而言，是单位元r*=(r+)*运算*和的关系r*=r*运算符*是幂等的 现在学习的是第29页，共37页1.3 正规表达式（正规式正规表达式（正规式）正规式和正规集之间并不存在一一对应的关系。不同的正规式可能描述的是相同的正规集；例如：b(ab)*及(ba)*b都是b开头且其后跟以零个或任意多个

24、ab所组成的字符串两个正规式等价，当且仅当它们描述的正规集相同。=a,b上的a,b*上的任意一个子集不一定是正规集。例如，子集anbn|n 1就不是一个正规集，它不能用正规式来描述，也不能用正规文法（3型文法）来描述。因为正规文法和正规式均没有这样的能力来判断或保证a的个数等于b的个数。但它可用上下文无关文法（2型文法）S-aSb|ab来描述。王雷版权所有现在学习的是第30页，共37页1.3 正规表达式（正规式正规表达式（正规式）正规表达式运算符的优先级顺序正规表达式运算符的优先级顺序最高优先级的是闭包运算（星闭包*和正闭包+），它类似于代数运算中的幂运算。其次优先级的是“联结”运算符，它类似

25、于代数运算中的乘法。优先级别最低的是“并”运算（+运算符）。它类似于代数运算中的加法。通过在正规表达式中添加括号可以改变运算的优先级。王雷版权所有现在学习的是第31页，共37页1.4 正规文法与正规式正规文法与正规式一个正规语言可以由正规文法定义，也可由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对于每一个正规式，存在一个生成同一语言的正规文法。正规表达式和正规文法正规表达式和正规文法 之间是可以互相转换的。王雷版权所有现在学习的是第32页，共37页1.4 正规文法与正规式正规文法与正规式正规表达式转换成正规文法正规表达式转换成正规文法 将上的一个正规表达式r转换成正

26、规文法G=（V，T，S，P）的方法如下：1、令T=；2、选择一个非终结符S，生成规则S r，并将S定为G的开始符号。3、若x和y都是正规式，则：(1)对形如A xy的规则，重写成A xB,，B y两个规则，其中B是新选择的非终结符，即BV。(2)对形如A(x+y)B的规则，重写成A xB，A yB两个规则。(3)对形如Ax+y的规则，重写成A x，A y两个规则。(4)对已转换的文法中形如Ax*y的规则，重写成A xA，A y两个规则。4、不断利用上述规则进行变换，直到每一条规则最多有一个终结符为止。王雷版权所有现在学习的是第33页，共37页1.4 正规文法与正规式正规文法与正规式将正规文法转

27、换成正规式将正规文法转换成正规式基本上是上述过程的逆过程：将给定的正规文法G视为定义各非终结符所产生的正规集的一个联立方程组，再根据下面的求解规则来解此联立方程组以求得相应的正规式。例例1.8 考虑如下列正规文法G，该文法产生的语言是an bam|m,n1:S aS|aA S=aS+aA A bB A=bB (*)B aB|a B=aB+b王雷版权所有现在学习的是第34页，共37页1.4 正规文法与正规式正规文法与正规式将正规文法转换成正规式将正规文法转换成正规式可以用代入法来求解这个方程组，比如，用A=bB来代入S=aS+aA中的A。在上述正规文法G形成的方程中，总会遇到形如X=rX+t的方

28、程，也就是含有右递归的方程。读者可以自己证明，如果一个正规集是无穷集的话，那么它的右线性文法中就一定含有右递归。求解规则：求解规则：方程X=rX+t有形如X=r*t的解。王雷版权所有现在学习的是第35页，共37页1.4 正规文法与正规式正规文法与正规式将正规文法转换成正规式将正规文法转换成正规式证明：因为我们可注意到方程X=rX+t对应于右线性文法中如下的两个规则：X rX X t那么这两条规则所生成的语言显而易见为：LX=t,rt,rrt,=L(r*t)，故方程X=rX+t相应地有解X=r*t。因此，求解方程组(*)，可先对方程B=aB+b应用求解规则，求得B=a*b；然后将此解代入方程A=bB便可得到A=ba*b；然后再用ba*b代替方程S=aS+aA中的A，可得S=aS+aba*b。最后在应用求解规则得到S=a*aba*b。所求得的正规式a*aba*b所表示的语言与例1.8文法G所能产生的语言是相同的。王雷版权所有现在学习的是第36页，共37页王雷湘潭大学信息工程学院2012版权所有现在学习的是第37页，共37页