计算理论基础章1

计算理论基础信息科学与工程学院计算机软件与理论研究所许桂清杨莹序言一.本课的性质以及研究的内容•任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？•什么是计算机科学的基础？什么是计算机科学的基本问题？诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？•这些问题就是计算理论要讨论的问题。性质：该课是计算机科学的理论课。•计算理论：就是研究理论计算机的科学。•理论计算机：是研究计算机的理论模型，研究计算机的本质，也就是把计算机看成一个数学系统。(因为计算机科学的基本思想和模型在本质上是数学——离散的。)内容：•形式语言与自动机理论：正规文法与有限自动机(正规语言)、上下文无关文法与下推自动机(上下文无关语言)图灵机(递归可枚举语言)•可计算性理论：什么是可计算？•计算复杂性理论：时间复杂性、空间复杂性。•递归函数二.学习目的：•了解这些计算理论我们知道计算机不论从它的诞生还是它的快速发展过程都没有离开计算理论，也就是它是在计算理论指导下诞生和发展的。并课所涉及的都是计算机科学的基本问题。不首先了解它们，是很难理解计算机科学的。作为计算机科学与技术专业的本科生和研究生应该了解这些计算理论。•培养能力此外此课可以培养学生抽象逻辑思维和形式化思维的能力。•为学习《编译原理》做准备第一章形式语言概述语言是人们交流思想的工具。按照语言的形成，可将语言分成二类：自然语言和人工语言（形式语言）。一.自然语言如汉语、英语、法语、日语等等都是自然语言。形成：是大多数人经过长期地社会实践逐渐形成的。特点：种类繁多，内容丰富，表达能力强。缺点：具有地方性，不便互相交流。有时不够精确，有多义性。比如汉语中的“打”字，具有多种解释。如打伞、打扑克、打醋、打人、一打袜子等等。因此自然语言不适合计算机的程序设计语言。二.形式语言如计算机的各种程序设计语言、数理逻辑中的谓词演算语言等都属于形式语言。形成：是少数人经过严格地形式定义确定的语言。特点：定义准确，无歧义性。在五十年代Chomky建立了形式语言的理论体系，从此它发展很快，形式语言的研究已成为计算机科学的一个重要领域。形式语言：定义为一个严格的数学系统，其严格的形式性使我们能给出形式语言的数学描述，进而揭示所描述语言的结构、特性及其应用范围。描述形式语言有两种方法：•生成法•识别法。生成法：用文法给出产生该语言的所有句子的规则。根据这些规则可以产生语言中每个句子。这些规则就叫生成式或产生式。例如，下边是个描述“十进制数”的文法：G=({F,I,D,N},{.,0,1,2,3,4,5,6,7,8,9},P,F)令F——“十进制数”、I——“无符号整数”、D——“十进制小数”、N——“数字”于是该文法的产生式集合P中产生式如下：F→I|D|IDI→N|NID→.IN→0|1|2|3|4|5|6|7|8|9例如利用此文法产生3.14:FIDNDN.I3.I3.NI3.1I3.1N3.14识别法：核心是一个自动机。对于给定的符号串可以由自动机识别出是否为给定语言中合法的句子。自动机的具体的例子以后再介绍。1-1形式语言基本概念形式语言必须规定所用基本符号集合，这就是字母表。一.字母表字母表：符号的有限集合。通常用V或者表示。例如V＝a,b,c。二．符号串符号串：是由字母表中的符号组成的序列。例如，aabbcc就是上述字母表V上的一个符号串。符号串的长度：即是符号串所含符号个数。例如符号串＝aabbcc用表示的长度，则|＝6。空符号串：不含任何符号的符号串，通常用表示。显然＝0。三.符号串的“连接”运算“◦”例符号串x=abc，y=cba，x与y的连接构成符号串z,则z=x◦y=abc◦cba=abccba显然连接运算“◦”满足可结合性且有幺元，即对任何符号串x,y,z有(x◦y)◦z=x◦(y◦z)x◦=◦x=x对符号串的连接可以写成乘幂的形式，即对任何符号串x有：x◦x=x2x◦x◦x=x3一般地xn-1◦x=xnxm◦xn=xm+n(xm)n=xmn四．符号串集合的乘积令A和B是符号串的集合，A与B的乘积记作AB，且AB＝x◦yxAyB例如，A＝a,b,ab，B=0,1，则AB＝a0,b0,,ab0,a1,b1,ab1由于符号串集合的乘积的运算是可结合的，所以也可写成乘幂的形式。即A是符号串集合，则AA＝A2AmAn=Am+n(Am)n=Amn当两个集合中有一个集合是空集时，则它们的乘积为空集。即A=A=。五．字母表的闭包V与V*令V是个字母表。则V——由V中符号构成的长度为1的符号串的集合。V2——由V中符号构成的长度为2的符号串的集合。V3——由V中符号构成的长度为3的符号串的集合。于是Vk＝{w|w是由V中的符号构成的符号串，且|w|=k}V0={}V=VV2V3V4…V*=V0VV2V3V4…V*是由V中符号构成的任意长度的符号串(所有符号串)构成的集合。例如，V＝{0,1}V+={0,1,00,01,10,11,000,001,010,011,100,101,110,111,…}V*={,0,1,00,01,10,11,000,001,010,011,100,101,110,111,…}六．语言定义：设V是个字母表,LV*,则称L是V上的一个语言。例如，V＝{0,1}L1=ФL2={0,00,000，0000，00000，……}L3={1,11,111,1111,11111,……}上述L1、L2、L3都是V上的语言。七.句子设L是V上的语言，如果w∈Ｌ，则称w是Ｌ中的一个句子。例如，000就是L2中的一个句子。1.2文法概念文法是语言生成器中的最重要的一类，为了定义语言，文法不仅作为一个“装置”，给出语言的句子的结构，而且本身也是一个数学系统。例如：前边定义“十进制数”的文法。G=({F,I,D,N},{.,0,1,2,3,4,5,6,7,8,9},P,F)F—十进制数、I—无符号整数、D—十进制小数、N—数字于是该文法的产生式集合P中产生式如下：F→I|D|IDI→N|NID→.IN→0|1|2|3|4|5|6|7|8|9可见一个文法中有两种符号。非终极符终极符1.文法（Grammar）定义一个文法G是个有序四元组，记作Ｇ=（ＶＮ,ＶT,Ｐ,Ｓ），其中ＶＮ非终极符(变元)集合，用大写英文字母表示。ＶT终极符集合。这里ＶＮ∩ＶT=Ф。有时记作ＶＮ∪ＶT＝ＶＰ生成式(也叫产生式)的集合。产生式的形式:α→β，其中α∈V，β∈V*α→β的含义是：可以用符号串β代替符号串α。另外如果有α→β，α→γ，α→δ可简记成α→β｜γ｜δＳ开始变元，Ｓ∈ＶＮ。【例1-2.1】下面是定义只含有＋和*运算的算术表达式的文法。Ｇ１=（ＶＮ,ＶT,Ｐ,Ｅ）ＶＮ=｛Ｅ,Ｔ,Ｆ｝，ＶＴ＝｛ａ,ｂ,+,*,(，)｝Ｐ={Ｅ→Ｅ＋Ｔ，Ｅ→Ｔ，Ｔ→Ｔ*Ｆ，Ｔ→Ｆ，Ｆ→(Ｅ)，Ｆ→ａ，Ｆ→ｂ}【例1-2.2】Ｇ２=（{S},{0,1}，P，S）P={S→0S1|01}文法中使用的符号通常作如下约定：（1）用大写英文字母表示变元。S通常表示开始变元。（2）用小写的a,b,c,…表示终极符。（3）用x,y,z,…表示终极符串，即x,y,z,…∈ＶT*。（4）用α,β,γ,…希腊字母表示既含有终极符，也含有非终极符的符号串，即α,β,γ,…∈(ＶＮ∪ＶT)*。2.句型（Sententialform）设文法G=(ＶＮ,ＶT,Ｐ,S)，则（1）S是个句型。（2）若αβγ是个句型,且β→δ是Ｐ中的一个产生式，则αδγ也是一个句型。按此定义，对于文法Ｇ２来说，P＝{S→0S1|01}S，0S1，00S11，000111都是句型。3.句型的推导（派生）设文法G=(ＶＮ,ＶT,Ｐ,S)，若αβγ是G的一个句型，且β→δ∈Ｐ，则αδγ也是一个句型，我们就称为可由句型αβγ直接推导出αδγ,记作αβγGαδγ。如果没有其它文法，不会产生混淆的情况下，此推导可简记成αβγαδγ。符号“”表示句型之间的直接推导(派生)关系。如果有α1α2α3…αn，则表示由α1可以间接推导出αn，可以写成α1*αn,符号“*”表示句型之间经过多步间接推导的关系。符号“k”表示句型之间经过k步间接推导的关系。4.文法产生的语言设文法G=(ＶＮ,ＶＴ,Ｐ,S)，令集合L(G)={w|w∈ＶT*且Ｓ*w}则称L(G)是由G产生的语言。其中每个w∈L(G)是文法Ｇ产生的句子。在例1-2.2中，P={S→0S1|01}有S0S100S11000111,所以L(G2)={0n1n|n≥1}【例1-2.3】Ｇ3=({S,B,C},{a,b,c}，P，S)P:(1)S→aSBC(2)S→aBC(3)CB→BC(4)aB→ab(5)bB→bb(6)bC→bc(7)cC→cc【例1-2.3】Ｇ3=({S,B,C},{a,b,c}，P，S)P:(1)S→aSBC(2)S→aBC(3)CB→BC(4)aB→ab(5)bB→bb(6)bC→bc(7)cC→cc求L(Ｇ3)。解.S*an-1S(BC)n-1(产生式(1)使用n-1次)an(BC)n(产生式(2)使用一次)*anBnCn(产生式(3)使用多次)anbBn-1Cn(产生式(4)使用一次)*anbnCn(产生式(5)使用多次)anbncCn-1(产生式(6)使用一次)*anbncn(产生式(7)使用多次)所以L(G3)={anbncn|n≥1}【例1-2.4】Ｇ4=({S,A,B},{a,b}，P，S）P:S→aB|bA,A→a|aS|bAA,B→b|bS|aBB求证L(Ｇ4)中的每个句子里的a和b的个数相同。证明：令Na(w)表示w中a的个数，L={w|w∈{a,b}+且Na(w)=Nb(w)}只要证明L(Ｇ4)=L即可。1).先证L(Ｇ4)L先用归纳法(对G中推导Ｓ*α的步数n作归纳)证明如下结论：如果Ｓ*α，则Na+A(α)=Nb+B(α)。其中Na+A(α)表示α中a和A的个数总和。(1)当n=1时，此推导一定是用产生式S→aB|bA，于是有SaB或SbA。Na+A(aB)=Nb+B(bA),结论成立。(2)假设n≤k时，结论成立。即如果有Snα1(表示从S经n步推出α1)，则Na+A(α1)=Nb+B(α1)。(3)当n=k+1时，不妨设Ｓkα1α2，则由(2)得Na+A(α1)=Nb+B(α1)下面讨论推导α1α2，由于α1中的变元只有三种，所以分三种情况讨论：①此派生是对α1中的变元S作代换，必用产生式S→aB|bA，显然不论使用哪一个产生式，都能得出结论Na+A(α2)=Nb+B(α2)。②此派生是对α1中的变元A作代换，必用产生式A→a|aS|bAA,显然不论使用哪一个产生式，都能得出结论Na+A(α2)=Nb+B(α2)。③此派生是对α1中的变元B作代换，必用产生式B→b|bS|Abb，显然不论使用哪一个产生式，都能得出结论：Na+A(α2)=Nb+B(α2)。综上所述，上述命题成立。任取w∈L(Ｇ4)，于是有推导Ｓ*αw,由上述结论得Na+A(α)=Nb+B(α)而在最后一步推导αw中，要消去α中的变元，必用产生式A→a或B→b,显然仍有Na+A(w)=Nb+B(w),此时w中A和B的个数都为0，于是有Na(w)=Nb(w),所以w∈L，于是有L(Ｇ4)L。2)再证LL(Ｇ4)任取w∈L,显然Na(w)=Nb(w),令Na(w)=n,对n作归纳，证出w∈L(Ｇ4)。(1)n=1时，则w=ab,或w=ba，在Ｇ4中有推导：SaBab或SbAba，所以有w∈L(Ｇ4)(2)假设n≤k时，结论成立。即w∈L,Na(w)=Nb(w)，Na(w)≤k，则有w∈