计算机数学基础

计算机数学基础第一页，共三十七页，2022年，8月28日1.1符号、符号串及其运算字母表：一个非空的有限集合称为字母表，通常用或者大写的西文字母表示。字母表中的元素称作为字母或符号，一般用小写字母、数字等表示。符号串：一个符号串是由字母表中的字母组成的一个有限序列。符号串的长度：符号串所包含符号的个数称为符号串的长度。符号串w的长度记为|w|。空串：长度为0的符号串称为空串，用表示。王雷@版权所有第二页，共三十七页，2022年，8月28日1.1符号、符号串及其运算符号串的联结：联结是符号串的基本运算。两个符号串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中，显然有XY≠YX，(XY)X=X(YX)=112211。王雷@版权所有第三页，共三十七页，2022年，8月28日1.1符号、符号串及其运算由于是不含符号的符号串(空串)，所以对任意符号串X都有，X=X=X。由此我们可以认为是符号串联结运算的单位元。符号串的方幂：设X是符号串，把X自身联结n次后，得到的符号串Z，即Z=XX…XX=Xn，称为X的方幂。我们约定X0=。这个定义可以递归地表示为：AB王雷@版权所有第四页，共三十七页，2022年，8月28日1.1符号、符号串及其运算符号串的子串、前缀和后缀：符号串V是符号串W的子串，当且仅当存在符号串X和Y，使得W=XVY。这里，X和Y都可能是空串。集合的联结：设A和B都是符号串的集合，定以集合A和B的联结为：AB={XY|X∈A且Y∈B}，即集合A和B的联结是集合A中的符号串和集合B中的符号串的联结所构成的集合。

AB王雷@版权所有第五页，共三十七页，2022年，8月28日1.1符号、符号串及其运算集合的方幂：设A是符号串的集合，把A自身联结n次后，得到的新的集合An，即An=A…A…A，称为集合A的方幂。我们约定A0={}。这个定义可以递归地表示为：王雷@版权所有第六页，共三十七页，2022年，8月28日1.1符号、符号串及其运算集合的闭包和正闭包：设A是符号串的集合，用A*表示A的所有的有限次方幂的并集，则称A*为集合A上的闭包，即：注意：闭包A*与正闭包A+的差别在于是否包含空串。在闭包A*中去掉空串后就成为正闭包A+。A*具有可数无穷多的符号串。A*=A0∪A1∪A2∪…∪An∪…而称A+=A1∪A2∪…∪An∪…为A上的正闭包，显然,有A*=A0∪A+

，A+=A*A=AA*。语言：令为一个字母表。若L

*，则L是字母表上的一个语言。即：L为一个由字母表上的字符串所构成的集合。王雷@版权所有第七页，共三十七页，2022年，8月28日1.2文法与语言的形式定义语言都是用文法来描述的。一个文法实际上是一组有限的规则式。非终结符（一种过渡性符号）：也是一种符号，但不是字母表中的符号。我们将它记为V。终结符：是一个语言的字母表中的符号。我们将它记为T。对于一个形式语言L，设T和V分别是它的终结符集和非终结符集，显然有LT*，且T∩V=。王雷@版权所有第八页，共三十七页，2022年，8月28日1.2.1文法的形式化定义定义1.1：一条产生式是一个有序对(,),通常可写作如下形式∷=

或其中：∈V+，∈V’*，V’=V∪T。称为产生式的左部，称为产生式的右部。注意：∈V+说明是一个非终结符且≠，即产生式的左部不允许是空串。∈V’*说明产生式的右部是这样的一个符号串，它可以含有终结符，也可以含有非终结符，同时还可以为空串。王雷@版权所有第九页，共三十七页，2022年，8月28日1.2.1文法的形式化定义定义1.2：文法G定义为一个四元组G=(V，T，P，S),其中：1、V是一个非空的有穷集合，称为非终结符集。2、T是一个非空的有穷集合，称为终结符集，且V∩T=。3、P是一个非空的有穷的产生式的集合。4、S∈V，称为文法的开始符号，S至少要在P中的一条产生式中作为左部出现。王雷@版权所有第十页，共三十七页，2022年，8月28日1.2.1文法的形式化定义例1.2设文法G=({A,E}，{a}，P，A)，其中P={Aa，AaE，EaA}。在许多的文法中，有多条产生式的左部相同，可以将左部相同的产生式写成合并的产生式形式。在此例文法G中，P中的前两个产生式的左部相同，都是A，可以合并为Aa|aE，这样一来，P={Aa|aE，EaA}。在许多情况下，只需要将文法的产生式写出就可以表明该文法了。约定：第一条产生式的左部是文法的开始符

王雷@版权所有第十一页，共三十七页，2022年，8月28日1.2.2推导的形式化定义定义1.3：给定一个文法G=(V,T,P,S)，如果是G中的一条产生式，和是V’*中的任意符号，若存在符号串x,y满足：x=，y=，则称x使用了产生式直接产生了y，或者称y是x的直接推导，或者称y可以直接归约到x，记作xy。例：令x=aAb，y=acb，

=a，

=b，则y是x的直接推导，即：aAbacb，所使用的产生式为Ac。王雷@版权所有第十二页，共三十七页，2022年，8月28日1.2.2推导的形式化定义定义1.4：给定一个文法G=(V,T,P,S)，设x，yV*，如果：

1、存在如下的直接推导序列：x=w0w1w2…wn=y(n＞0)则称x推导出(产生)y，推导长度为n，或者称为y归约到x，记作xny。

2、我们用x+y表示存在n＞0且xny；用x*y表示有x+

y或者x=y。最左(右)推导：如果在推导的每一步xy，都是对x中的最左(右)边的非终结符选用产生式进行替换，则这种推导称为最左(右)推导。最右推导也称为规范推导。王雷@版权所有第十三页，共三十七页，2022年，8月28日1.2.2推导的形式化定义规范句型、短语、直接短语和句柄定义1.5：给定一个文法G=(V,T,P,S)，如果符号串x是从文法G的开始符号S推导出来的，即S*x，则称x是文法G的句型。如果符号串x是仅由终结符组成的句型，即S*x且x∈T*，则称x是文法G的句子。由规范推导所得到的句型就称之为规范句型。王雷@版权所有第十四页，共三十七页，2022年，8月28日1.2.2推导的形式化定义规范句型、短语、直接短语和句柄定义1.6

设G[S]是一文法，x=w是一句型，如果：S*A且A*

w则称w是句型x的一个相对于非终结符A的短语；如果：S*A且Aw则称w是句型x的一个相对于非终结符Ａ的直接短语(或简单短语)；如果w是一个句型x的最左直接短语，称w为句型x的句柄。王雷@版权所有第十五页，共三十七页，2022年，8月28日1.2.3语言的形式化定义定义1.7：给定一个文法G=(V,T,P,S)，由G所生成的语言记作L(G)，令L(G)={x|S+x且x∈T*}，其中x称为语言L(G)的句子。即：L(G)是一个由从文法G的开始符号S所推导出来的所有句子所构成的集合。例1.3给定文法G[S]：SaSb|ab

由该文法生成的任何一个句子都是：先使用产生式SaSb若干次得到：SaSbaaSbb…an-1Sbn-1

，即S+an-1Sbn-1

；再使用产生式Sab一次得到：S+an-1Sbn-1

anbn。不难对推导的步数用数学归纳法证明该文法推导的所有符号串都是anbn的形式。另一方面，我们也不难对符号串的长度用数学归纳法证明，对任何形式为anbn，n≥1，的符号串，一定可以用文法G[S]推导出来，即存在推导S+anbn。所以，L(G[S])={anbn|n1}。王雷@版权所有第十六页，共三十七页，2022年，8月28日1.2.3语言的形式化定义例1.4设文法G[V]：VaVb，VbbW，abWc。求文法G[V]所生成的语言。解：V是文法的开始符。继续多次使用该产生式，得到的推导结果是：anVbn，n≥1。在anVbn中，为了消除非终结符V，必须使用产生式VbbW，得到推导结果是：anbWbn-1=an-1abWbn-1，n≥1。只有使用产生式abWc，才能消除非终结符W，最终得到推导结果：an-1cbn-1，n≥1。另一方面，不难证明，对任何形式为ancbn，n≥0的符号串都可以用文法G[V]推导出来。因此，文法G[V]生成的语言为：L(G[V])={an-1cbn-1|n≥1}={ancbn|n≥0}。王雷@版权所有第十七页，共三十七页，2022年，8月28日1.2.3语言的形式化定义例1.5文法G[A]：AaR，Aab，RAb所生成的语言L(G[A])={anbn|n1}。(留做课后习题)。从上面可以看出，尽管文法G[A]与例1.7中的文法G[S]是两个不同的文法，但是所生成的语言是相同，都是{anbn|n1}。定义1.8

给定任意两个文法G1、G2，如果它们所生成语言相同，即：L(G1)=L(G2)，则称文法G1与G2是等价的。王雷@版权所有第十八页，共三十七页，2022年，8月28日1.2.4语法树语法树是句型推导过程的图形表示。例如，设句子bd0的最右推导或规范推导为：<标识符><标识符><数字><标识符>0<标识符><字母>0<标识符>d0<字母>d0bd0王雷@版权所有<标识符><数字><标识符><标识符><字母><字母>bd0图1.2句子bd0的语法树第十九页，共三十七页，2022年，8月28日1.2.4语法树定义1.9如果一个文法存在某个句子对应两棵以上的不同的语法树，或有两个以上的不同的最左(右)推导，则称该文法是二义性文法（程序设计语言不能有二义性）。定义1.10如果一个语言L的任何文法都是二义性文法，则称该语言L是二义性语言。在理论上已经证明了，存在着这种二义性的语言。

文法的二义性与语言的二义性是两个不同的概念。AB王雷@版权所有第二十页，共三十七页，2022年，8月28日1.2.5文法和语言的类型Chomsky于1956年把文法分成四种类型，即：0型文法、1型文法、2型文法和3型文法。这种文法的分类称作Chomsky分类。文法所生成的语言，根据四种类型文法，也分为四种，即：0型语言、1型语言、2型语言和3型语言。Chomsky建立的形式语言理论对计算机科学的发展规律有着深刻的影响，特别是对计算机程序设计语言的设计、编译方法和计算复杂性等方面具有更大的作用。王雷@版权所有诺姆·乔姆斯基（NoamChomsky,1928--），美国语言学家，转换-生成语法的创始人。1928年12月7日出生于美国宾夕法尼亚州的费城。1947年，在哈里斯的影响下他开始研究语言学。1951年在宾夕法尼亚大学完成硕士论文《现代希伯莱语语素音位学》，1955年在该校完成博士论文《转换分析》，获得博士学位。从1955年秋天开始，他一直在麻省理工学院工作，曾任该校语言学与哲学系主任，并任该校认知科学研究中心主任，为语言学界培养了一批有素养的学者。第二十一页，共三十七页，2022年，8月28日1.2.5文法和语言的类型定义1.11设文法G=(V,T,P,S)，如果，对于P，满足(V∪T)+且中至少含有一个非终结符，(V∪T)*，则G称为0型文法（或短语结构文法，简记为PSG)或者无约束文法(UnrestrictedGrammar)。0型文法能确保产生式的左部不为空。由0型文法所生成的语言称为0型语言或短语结构语言（简记为PSL）。0型文法的能力与图灵机（TuringMachine）相当。王雷@版权所有第二十二页，共三十七页，2022年，8月28日1.2.5文法和语言的类型定义1.12设文法G=(V,T,P,S)，如果对于P，满足||≥||(除S外)，则文法G称为1型文法或上下文有关文法，简记为CSG。1型文法的产生式的形式也被描述为：1A212，其中：1、2

、(V∪T)+，AV。它更能体现“上下文有关”这一含义，因为，只有A出现在1和2之间（1为A的上文，2为A的下文），才允许用来取代A。1型文法所产生的语言称作1型语言或上下文有关语言(简记为CSL)。王雷@版权所有第二十三页，共三十七页，2022年，8月28日1.2.5文法和语言的类型定义1.13设文法G=(V,T,P,S)，如果，对于P，满足V，(V∪T)*，则称G为2型文法或上下文无关文法，简记为CFG。上下文无关文法取名为“上下文无关”的原因就是因为字符总可以被字串自由替换，而无需考虑字符出现的上下文。2型文法所产生的语言称作2型语言或上下文无关语言(简记为CFL)。一个简单的上下文无关文法的例子是：S->aSb|ε。由于这个文法的产生式的左边都是单个的非终结符S，右边是由终结符或非终结符构成的符号串aSb和ε，因此符合上下文无关语法产生式的要求。该文法产生的语言为{anbn:n≥0}。王雷@版权所有第二十四页，共三十七页，2022年，8月28日1.2.5文法和语言的类型定义1.14：设文法G=(V,T,P,S)，如果P中的每一条产生式都是AaB或Aa形式，其中：A、BV，aT，则称G为3型文法或正规文法,简记为RG。3型文法所产生的语言称作3型语言或正规语言(简记为RL)。3型语言与有限自动机等价，即有限自动机恰能识别3型语言。0型语言1型语言2型语言3型语言图1.4形式语言的Chomsky层级在忽略句子ε的情况下，由Chomsky分类定义可知，任何3型语言都是2型语言，任何2型语言都是1型语言，任何1型语言都是0型语言。王雷@版权所有第二十五页，共三十七页，2022年，8月28日1.2.5文法和语言的类型王雷@版权所有0型语言1型语言2型语言3型语言图1.4形式语言的Chomsky层级第二十六页，共三十七页，2022年，8月28日1.3正规表达式（正规式

）正规式是按照一组定义规则，由较简单的正规式构成的，每个正规式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）e1·e2也是正规表达式，它所表示的正规集为

L(e1·e2)=L(e1)L(e2)

（3）(e1)*也是正规表达式，它所表示的正规集为

L((e1)*)=(L(e1))*王雷@版权所有第二十七页，共三十七页，2022年，8月28日1.3正规表达式（正规式

）例1.7

令∑={a,b}，下面表列出了∑上的一些正规表达和相应的正规集：王雷@版权所有正规表达式正规集a+b{a,b}a*{,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串第二十八页，共三十七页，2022年，8月28日1.3正规表达式（正规式

）正规式的代数性质王雷@版权所有公理说明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*运算符*是幂等的第二十九页，共三十七页，2022年，8月28日1.3正规表达式（正规式

）正规式和正规集之间并不存在一一对应的关系。不同的正规式可能描述的是相同的正规集；例如：b(ab)*及(ba)*b都是b开头且其后跟以零个或任意多个ab所组成的字符串两个正规式等价，当且仅当它们描述的正规集相同。

={a,b}上的{a,b}*上的任意一个子集不一定是正规集。例如，子集{anbn|n1}就不是一个正规集，它不能用正规式来描述，也不能用正规文法（3型文法）来描述。因为正规文法和正规式均没有这样的能力来判断或保证a的个数等于b的个数。但它可用上下文无关文法（2型文法）S->aSb|ab来描述。王雷@版权所有第三十页，共三十七页，2022年，8月28日1.3正规表达式（正规式

）正规表达式运算符的优先级顺序最高优先级的是闭包运算（星闭包*和正闭包+），它类似于代数运算中的幂运算。其次优先级的是“联结”运算符，它类似于代数运算中的乘法。优先级别最低的是“并”运算（+运算符）。它类似于代数运算中的加法。通过在正规表达式中添加括号可以改变运算的优先级。王雷@版权所有第三十一页，共三十七页，2022年，8月28日1.4正规文法与正规式一个正规语言可以由正规文法定义，也可由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对于每一个正规式，存在一个生成同一语言的正规文法。正规表达式和正规文法之间是可以互相转换的。王雷@版权所有第三十二页，共三十七页，2022年，8月28日1.4正规文法与正规式正规表达式转换成正规文法将∑上的一个正规表达式r转换成正规文法G=（V，T，S，P）的方法如下：

1、令T=∑；

2、选择一个非终结符S，生成规则Sr，并将S定为G的开始符号。

3、若x和y都是正规式，则：

(1)对形如Axy的规则，重写成AxB,，By两个规则，其中B是新选择的非终结符，即B∈V。

(2)对形如A(x+y)B的规则，重写成AxB，AyB两个规则。

(3)对形如Ax+y的规则，重写成Ax，Ay两个规则。

(4)对已转换的文法中形如Ax*y的规则，重写成AxA，Ay两个规则。4、不断利用上述规则进行变换，直到每一条规则最多有一个终