计算理论基础信息科学与工程学院计算机软件与理论研究所许桂清 杨莹序 言一一. 本课的性质以及研究的内容本课的性质以及研究的内容任何一门学科都有它的基础和它的基本问题，如物质的任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？本质是什么？有机体生命的基础和起源是什么？什么是计算机科学的基础？什么是计算机科学的基本问什么是计算机科学的基础？什么是计算机科学的基本问题？题？ 诸如什么是形式语言？什么是计算？什么是能计算的诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？么是可判定的？什么是不可判定的？这些问题就是计算理论要讨论的问题。这些问题就是计算理论要讨论的问题。性质性质：该课是计算机科学的理论课。：该课是计算机科学的理论课。计算理论计算理论：就是研究理论计算机的科学。：就是研究理论计算机的科学。理论计算机理论计算机：是研究计算机的理论模型，研究计算机：是研究计算机的理论模型，研究计算机的本质，也就是把计算机看成一个数学系统。的本质，也就是把计算机看成一个数学系统。(因为计算因为计算机科学的基本思想和模型在本质上是数学机科学的基本思想和模型在本质上是数学离散的。离散的。)内容内容：形式语言与自动机理论：形式语言与自动机理论： 正规文法与有限自动机正规文法与有限自动机(正规语言正规语言) 、 上下文无关文法与下推自动机上下文无关文法与下推自动机(上下文无关语言上下文无关语言) 图灵机图灵机(递归可枚举语言递归可枚举语言)可计算性理论：可计算性理论： 什么是可计算？什么是可计算？计算复杂性理论：计算复杂性理论： 时间复杂性时间复杂性 、 空间复杂性。空间复杂性。递归函数递归函数二二. 学习目的学习目的：了解这些计算理论了解这些计算理论 我们知道计算机不论从它的诞生还是它的快速发展过程我们知道计算机不论从它的诞生还是它的快速发展过程都没有离开计算理论，也就是它是在计算理论指导下诞生都没有离开计算理论，也就是它是在计算理论指导下诞生和发展的。并课所涉及的都是计算机科学的基本问题。不和发展的。并课所涉及的都是计算机科学的基本问题。不首先了解它们，是很难理解计算机科学的。作为计算机科首先了解它们，是很难理解计算机科学的。作为计算机科学与技术专业的本科生和研究生应该了解这些计算理论。学与技术专业的本科生和研究生应该了解这些计算理论。培养能力培养能力 此外此课可以培养学生抽象逻辑思维和形式化思维的能此外此课可以培养学生抽象逻辑思维和形式化思维的能力。力。为学习编译原理做准备为学习编译原理做准备第一章形式语言概述 语言是人们交流思想的工具。按照语言的形成，可将语言是人们交流思想的工具。按照语言的形成，可将语言分成二类：自然语言和人工语言（形式语言）。语言分成二类：自然语言和人工语言（形式语言）。一一. 自然语言自然语言如汉语、英语、法语、日语等等都是自然语言。如汉语、英语、法语、日语等等都是自然语言。 形成形成：是大多数人经过长期地社会实践逐渐形成的。：是大多数人经过长期地社会实践逐渐形成的。 特点特点：种类繁多，内容丰富，表达能力强。：种类繁多，内容丰富，表达能力强。 缺点缺点：具有地方性，不便互相交流。有时不够精确，：具有地方性，不便互相交流。有时不够精确，有多义性。比如汉语中的有多义性。比如汉语中的“打打”字，具有多种解释。如字，具有多种解释。如打打伞、打扑克、打醋、打人、一打袜子等等。因此自然语伞、打扑克、打醋、打人、一打袜子等等。因此自然语言不适合计算机的程序设计语言言不适合计算机的程序设计语言。二二.形式语言形式语言 如计算机的各种程序设计语言、数理逻辑中的谓词演如计算机的各种程序设计语言、数理逻辑中的谓词演算语言等都属于形式语言。算语言等都属于形式语言。 形成形成：是少数人经过严格地形式定义确定的语言。：是少数人经过严格地形式定义确定的语言。 特点特点：定义准确，无歧义性。：定义准确，无歧义性。 在五十年代在五十年代Chomky建立了形式语言的理论体系，从此建立了形式语言的理论体系，从此它发展很快，形式语言的研究已成为计算机科学的一个它发展很快，形式语言的研究已成为计算机科学的一个重要领域。重要领域。 形式语言：形式语言：定义为一个严格的数学系统，其严格的形定义为一个严格的数学系统，其严格的形式性使我们能给出形式语言的数学描述，进而揭示所描式性使我们能给出形式语言的数学描述，进而揭示所描述语言的结构、特性及其应用范围。述语言的结构、特性及其应用范围。 描述形式语言有两种方法描述形式语言有两种方法： 生成法生成法 识别法。识别法。生成法：生成法：用文法给出产生该语言的所有句子的规则。根用文法给出产生该语言的所有句子的规则。根据这些规则可以产生语言中每个句子。这些规则就叫生据这些规则可以产生语言中每个句子。这些规则就叫生成式或产生式。成式或产生式。例如，下边是个描述例如，下边是个描述“十进制数十进制数”的文法：的文法： G=(F,I,D,N, .,0,1,2,3,4,5,6,7,8,9, P, F)令令F“十进制数十进制数”、 I“无符号整数无符号整数”、 D“十进制小数十进制小数”、 N“数字数字”于是该文法的产生式集合于是该文法的产生式集合P中产生式如下：中产生式如下： FI|D|ID IN|NI D.I N0|1|2|3|4|5|6|7|8|9例如利用此文法产生例如利用此文法产生3.14:FIDNDN.I3.I3.NI3.1I3.1N3.14识别法：核心是一个自动机。对于给定的符号串可以核心是一个自动机。对于给定的符号串可以由自动机识别出是否为给定语言中合法的句子。由自动机识别出是否为给定语言中合法的句子。 自动机的具体的例子以后再介绍。自动机的具体的例子以后再介绍。1-1 形式语言基本概念 形式语言必须规定所用基本符号集合，这就是字母表。形式语言必须规定所用基本符号集合，这就是字母表。一一.字母表字母表 字母表字母表：符号的有限集合。通常用：符号的有限集合。通常用V或者或者 表示。表示。 例如例如 V a,b,c 。二二 符号串符号串 符号串符号串：是由字母表中的符号组成的序列。：是由字母表中的符号组成的序列。 例如，例如，aabbcc就是上述字母表就是上述字母表V上的一个符号串。上的一个符号串。 符号串的长度符号串的长度：即是符号串所含符号个数。：即是符号串所含符号个数。 例如符号串例如符号串 aabbcc 用用表示表示 的长度，则的长度，则 |6。 空符号串空符号串：不含任何符号的符号串，通常用：不含任何符号的符号串，通常用 表示。表示。 显然显然0 。三三.符号串的符号串的“连接连接”运算运算“” 例符号串例符号串x=abc，y=cba，x与与y的连接构成符号串的连接构成符号串z, 则则 z=xy=abccba=abccba 显显然然连连接接运运算算“”满满足足可可结结合合性性且且有有幺幺元元 ，即即对对任任何何符符号串号串x,y,z有有 (xy)z=x(yz) x = x=x 对符号串的连接可以写成乘幂的形式，即对任何符号串对符号串的连接可以写成乘幂的形式，即对任何符号串x有：有： xx=x2 xxx=x3一般地一般地 xn-1x=xn xm xn =xm+n ( xm)n=xmn四符号串集合的乘积四符号串集合的乘积 令令A和和B是符号串的集合，是符号串的集合，A与与B的乘积记作的乘积记作AB，且且 AB xy x A y B 例如，例如，A a,b,ab ，B= 0,1 ， 则则 AB a0,b0,ab0,a1,b1,ab1 由于符号串集合的乘积的运算是可结合的，所以也可由于符号串集合的乘积的运算是可结合的，所以也可写成乘幂的形式。即写成乘幂的形式。即A是符号串集合，则是符号串集合，则 AAA2 AmAn= Am+n (Am)n=Amn 当两个集合中有一个集合是空集时，则当两个集合中有一个集合是空集时，则 它们的乘积为它们的乘积为空集。即空集。即 A=A = 。五字母表的闭包五字母表的闭包V 与与V* 令令V是个字母表。则是个字母表。则 V由由V中符号构成的长度为中符号构成的长度为1的符号串的集合。的符号串的集合。 V2由由V中符号构成的长度为中符号构成的长度为2的符号串的集合。的符号串的集合。 V3由由V中符号构成的长度为中符号构成的长度为3的符号串的集合。的符号串的集合。于是于是 Vkw|w是由是由V中的符号构成的符号串，且中的符号构成的符号串，且|w|=k V0= V =V V2 V3 V4 V*=V0 V V2 V3 V4 V*是由是由V中符号构成的任意长度的符号串中符号构成的任意长度的符号串(所有符号串所有符号串)构成的集合。构成的集合。例如，例如，V0,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上的一个语言。上的一个语言。 例如，例如，V0,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中产生式如下：中产生式如下： FI|D|ID IN|NI D.I N0|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=S0S1|01文法中使用的文法中使用的符号符号通常作如下通常作如下约定约定：（1）用大写英文字母表示变元。用大写英文字母表示变元。S通常表示开始变元。通常表示开始变元。（2）用小写的用小写的a,b,c,表示终极符。表示终极符。（3）用用x,y,z,表示终极符串，即表示终极符串，即x,y,z,T*。（4）用用,希腊字母表示既含有终极符，也含有希腊字母表示既含有终极符，也含有非终极符的符号串，即非终极符的符号串，即,( T)*。2.句型（句型（Sentential form） 设文法设文法 G =(,T ,S)，则则（1）S是个句型。是个句型。（2）若）若是个句型是个句型,且且是中的一个产生式，是中的一个产生式，则则也是一个句型。也是一个句型。 按此定义，对于文法按此定义，对于文法来说，来说， PS0S1|01 S，0S1，00S11，000111都是句型。都是句型。3.句型的推导（派生） 设文法设文法G=( ,T ,S)，若若是是G的一个句型，的一个句型，且且，则，则也是一个句型，我们就称为可也是一个句型，我们就称为可由句型由句型直接推导直接推导出出,记作记作G。如果没有其它文法，不会产生混淆的情况下，此推导可如果没有其它文法，不会产生混淆的情况下，此推导可简记成简记成。 符号符号“”表示句型之间的直接推导表示句型之间的直接推导(派生派生)关系。关系。 如果有如果有123n ，则表示由则表示由1可以可以间间接推导接推导出出n ，可以写成可以写成1 * n , 符号符号“*”表示句型之间经过多步间接推导的关系。表示句型之间经过多步间接推导的关系。 符号符号“k”表示句型之间经过表示句型之间经过k步间接推导的关系。步间接推导的关系。4. 文法产生的语言文法产生的语言 设文法设文法 G =(,S)，令集合令集合 L(G)=w|wT*且且* w则称则称L(G)是由是由G产生的语言。产生的语言。 其中每个其中每个wL(G)是文法产生的句子。是文法产生的句子。 在在例例1-2.2中，中，P=S0S1|01 有有 S0S100S11000111, 所以所以L(G2)=0n1n|n1【例例1-2.3】 3 =(S,B,C,a,b,c，P，S)P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc【例例1-2.3】 3 =(S,B,C,a,b,c，P，S) P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc求求L(3)。解解. S *an-1S(BC)n-1 ( 产生式产生式(1)使用使用n-1次次) an(BC)n ( 产生式产生式(2)使用一次使用一次) *an Bn Cn ( 产生式产生式(3)使用多次使用多次) anbBn-1 Cn ( 产生式产生式(4)使用一次使用一次) *an bn Cn ( 产生式产生式(5)使用多次使用多次) an b ncCn-1 ( 产生式产生式(6)使用一次使用一次) *an bn cn ( 产生式产生式(7)使用多次使用多次)所以所以 L(G3)=a n bn cn| n1【例例1-2.4】 4 =(S,A,B,a,b，P，S） P: SaB|bA , Aa|aS|bAA , Bb|bS|Abb求证求证 L(4)中的每个句子里的中的每个句子里的a和和b的个数相同。的个数相同。证明证明：令：令Na(w)表示表示w中中a的个数，的个数， L= w | wa,b+且且Na(w)= Nb(w)只要证明只要证明L(4)=L 即可。即可。1).先证先证 L(4) L 先用归纳法先用归纳法(对对G中推导中推导*的步数的步数n作归纳作归纳)证明如证明如下结论：下结论： 如果如果 *，则则 Na+A()=()=Nb+B()()。 其中其中Na+A()()表示表示中中a a和和A A的个数总和。的个数总和。 (1) 当当n=1时，此推导一定是用产生式时，此推导一定是用产生式 SaB|bA ，于是于是有有 SaB 或或 SbA 。 Na+A(aB)= Nb+B(bA) , 结论成立。结论成立。(2) 假设假设nk 时，结论成立。即如果有时，结论成立。即如果有S n1 (表示从表示从S 经经n步推出步推出1)， 则则 Na+A(1)= Nb+B(1) 。(3) 当当 n=k+1 时，不妨设时，不妨设k12 ，则由则由(2)得得 Na+A(1)= Nb+B(1) 下面讨论推导下面讨论推导12 ，由于由于1中的变元只有三种，中的变元只有三种，所以所以分三种情况讨论分三种情况讨论： 此派生是对此派生是对1中的变元中的变元S作代换，必用产生式作代换，必用产生式SaB|bA ，显然不论使用哪一个产生式，都能得出结论显然不论使用哪一个产生式，都能得出结论Na+A(2)= Nb+B(2)。 此派生是对此派生是对1中的变元中的变元A作代换，必用产生式作代换，必用产生式Aa|aS|bAA , 显然不论使用哪一个产生式，都能得出结显然不论使用哪一个产生式，都能得出结论论Na+A(2)= Nb+B(2)。 此派生是对此派生是对1中的变元中的变元B作代换，必用产生式作代换，必用产生式Bb|bS|Abb ，显然不论使用哪一个产生式，都能得出显然不论使用哪一个产生式，都能得出结论：结论：Na+A(2)= Nb+B(2)。 综上所述，上述命题成立。综上所述，上述命题成立。 任取任取wL(4)，于是有推导，于是有推导* w ,由上述结论得由上述结论得Na+A()= Nb+B() 而在最后一步推导而在最后一步推导w中，中， 要消去要消去中的变元，必中的变元，必用产生式用产生式Aa或或Bb ,显然仍有显然仍有Na+A(w)= Nb+B(w),此时此时w中中A和和B的个数都为的个数都为0，于是有，于是有Na(w)= Nb(w),所以所以wL，于是有于是有 L(4) L 。2) 再证再证 L L(4) 任取任取wL ,显然显然Na(w)= Nb(w),令令Na(w)=n ,对对n作归纳，作归纳，证出证出wL(4)。 (1) n=1 时，则时，则w=ab,或或w=ba，在在4中有推导：中有推导： SaBab或或SbAba，所以有所以有 wL(4)(2) 假设假设nk时，结论成立。即时，结论成立。即wL, Na(w)=Nb(w)，Na(w)k，则有则有wL(4)， 即即4中有推导中有推导*w 。(3) 当当n=k+1时，时，(即即Na(w)= k+1,)，因为因为w中的最左符号不中的最左符号不是是a就是就是b。 下面下面分两种情况讨论分两种情况讨论。 a) w的的最左符号是最左符号是a ,不妨设不妨设w=aibx ,(i1), xa,b+, 如果如果i=1，w=abx , 则则Na(x)=Nb(x),且且 Na(x)=k ,由假设由假设(2)得得 xL(4)， 所以所以 S*x ,于是有推导：于是有推导： SaBabS*abx =w , 所以所以wL(4)。 如果如果i1, w=aibx，可将可将w写成写成w=aibw1bw2bwi，其中其中 Na(wj)=Nb(wj) (1ji), 这些这些wj中，可能中，可能wj=或或wjL。 如果如果wjL，又又Na(wj)k，由归纳假设得由归纳假设得wjL(4)， 即即S*wj 于是在于是在4中有推导：中有推导： SaBaaBB*aiBi , 再往下推导。再往下推导。 SaBaaBB*aiBi , 再往下推导。再往下推导。 如果如果w wj j=，则对应的第则对应的第j j个个B B可用产生式可用产生式BbBb替换，可替换，可 得得B Bbwbwj j。 如果如果 wj,则对应得第则对应得第j 个个B可用产生式可用产生式BbS替换，替换， 又因为又因为S * wj,可得可得B *bwj，最后得推导：最后得推导： SaBaaBB*aiBi*aibw1Bi-1* aibw1bw2Bi-2 * aibw1 bw2bw3bwi=w 即有即有 S*w , wL(4) 。 b) 当当w的的最左符号是最左符号是b时，不妨设时，不妨设w=biax (i1), xa,b+，类似可证。类似可证。 于是，对于于是，对于n=k+1 n=k+1 时，命题成立。时，命题成立。 即，如果即，如果wLwL，则则wL(wL(4 4),),所以所以 L LL(L(4 4) )。 最后得，最后得，L=L(L=L(4 4) )=w|wa,bw|wa,b+ +且且N Na a(w)= (w)= N Nb b(w)(w)。 1-3 文法的分类文法的分类 按照文法的产生式的结构不同，将文法分成按照文法的产生式的结构不同，将文法分成四类，称之为四类，称之为Chomsky分类。分类。 分别称之为分别称之为0型、型、1型、型、2型、型、3型。型。 令文法令文法 G =(,S) T, 具体的结构形式如下表所示：具体的结构形式如下表所示：类型类型 文文 法法 结结 构构 产产 生生 式式 形形 式式 限限 制制 条条 件件 0 短语结构文法短语结构文法 +,* Phrase Structure 上下文有关文法上下文有关文法 1A212 |12|1A2| 1 Context Sensitive 1，2* （CSG ） A , + 上下文无关文法上下文无关文法 A A,*2 Context Free （CFG） 正正 右线性文法右线性文法 AxB，Cy A,B,C 3 规规 文文 左线性文法左线性文法 ABx，Cy x,yT* 法法 按照此定义，判定上一节给定的四个文法是何类型：按照此定义，判定上一节给定的四个文法是何类型：=( ,T ,) =,， ,+,*,(，) =， *， ()， ，=(S,0,1，P，S) P=S0S1|013 =(S,B,C,a,b,c，P，S) P: (1) SaSBC (2) SaBC (3) CBBC (4) aBab (5) bBbb (6) bCbc (7) cCcc4=(S,A,B,a,b，P，S） P: SaB|bA , Aa|aS|bAA , Bb|bS|Abb G1、G2、G4是是2型文法，即上下文无关文法，型文法，即上下文无关文法， 而文法而文法G3是是0型文法。型文法。四种文法所产生的语言四种文法所产生的语言，分别叫作，分别叫作0型语言型语言递归可枚举集递归可枚举集(r.e) (recursively enumerable set)1型语言型语言上下文有关语言上下文有关语言(CSL) (Context Sensitive Language)2型语言型语言上下文无关语言上下文无关语言(CFL) (Context Free Language)3型语言型语言正规集正规集 (regular set)可以看出，各类文法之间有向上兼容性，即可以看出，各类文法之间有向上兼容性，即3型语言型语言 2型语言型语言 1型语言型语言 0型语言。型语言。文法与自动机之间的对应关系文法与自动机之间的对应关系： 识别这些语言的自动机分别是：识别这些语言的自动机分别是： 0型语言型语言 图灵机图灵机 1型语言型语言(CSL)线性界限自动机线性界限自动机 2型语言型语言(CFL)下推自动机下推自动机 3型语言型语言(正规集正规集)有限自动机有限自动机 有限自动机、下推自动机以及图灵机的内容后边有限自动机、下推自动机以及图灵机的内容后边将详细介绍。将详细介绍。本章重点：掌握文法概念和类型。本章重点：掌握文法概念和类型。作业题作业题：1给定文法给定文法G=(S,B,C,D,E,0,1,P,S)，其中其中P： SABC，AB0AD，AB1AE，AB，D00D，D11D，E00E， E11E， C， DCB0C，ECB1C，0BB0，1BB1试写出句子试写出句子01100110的派生过程。的派生过程。2设计下列各文法设计下列各文法G，使得它们分别是：使得它们分别是：（1）G是个上下文无关文法，且是个上下文无关文法，且L(G)=aibj ck i,j,k1。（2）G是个正规文法，且是个正规文法，且L(G)=aibj ck i,j,k1。（3）G是个上下文无关文法，且是个上下文无关文法，且L(G)= wwRw0,1+ 。其中其中wR是是w的逆转，例的逆转，例如如w=001, 则则wR=100.