计算理论课件第一章

计算理论课件第一章

ID:42277312

大小:200.56 KB

页数:31页

时间:2019-09-11

计算理论课件第一章_第1页
计算理论课件第一章_第2页
计算理论课件第一章_第3页
计算理论课件第一章_第4页
计算理论课件第一章_第5页
资源描述:

《计算理论课件第一章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、计算理论基础信息科学与工程学院计算机软件与理论研究所许桂清杨莹序言一.本课的性质以及研究的内容任何一门学科都有它的基础和它的基本问题,如物质的本质是什么?有机体生命的基础和起源是什么?什么是计算机科学的基础?什么是计算机科学的基本问题?诸如什么是形式语言?什么是计算?什么是能计算的?什么是不能计算的?什么是算法?如何评价算法?什么样的算法是可行的?这些问题能否判定?这又引出什么是可判定的?什么是不可判定的?这些问题就是计算理论要讨论的问题。性质:该课是计算机科学的理论课。计算理论:就是研究理论计算机的科学。理论计算机:是研究计算机的理论模型,

2、研究计算机的本质,也就是把计算机看成一个数学系统。(因为计算机科学的基本思想和模型在本质上是数学——离散的。)内容:形式语言与自动机理论:正规文法与有限自动机(正规语言)、上下文无关文法与下推自动机(上下文无关语言)图灵机(递归可枚举语言)可计算性理论:什么是可计算?计算复杂性理论:时间复杂性、空间复杂性。递归函数二.学习目的:了解这些计算理论我们知道计算机不论从它的诞生还是它的快速发展过程都没有离开计算理论,也就是它是在计算理论指导下诞生和发展的。并课所涉及的都是计算机科学的基本问题。不首先了解它们,是很难理解计算机科学的。作为计算机科学与

3、技术专业的本科生和研究生应该了解这些计算理论。培养能力此外此课可以培养学生抽象逻辑思维和形式化思维的能力。为学习《编译原理》做准备第一章形式语言概述语言是人们交流思想的工具。按照语言的形成,可将语言分成二类:自然语言和人工语言(形式语言)。一.自然语言如汉语、英语、法语、日语等等都是自然语言。形成:是大多数人经过长期地社会实践逐渐形成的。特点:种类繁多,内容丰富,表达能力强。缺点:具有地方性,不便互相交流。有时不够精确,有多义性。比如汉语中的“打”字,具有多种解释。如打伞、打扑克、打醋、打人、一打袜子等等。因此自然语言不适合计算机的程序设计语

4、言。二.形式语言如计算机的各种程序设计语言、数理逻辑中的谓词演算语言等都属于形式语言。形成:是少数人经过严格地形式定义确定的语言。特点:定义准确,无歧义性。在五十年代Chomky建立了形式语言的理论体系,从此它发展很快,形式语言的研究已成为计算机科学的一个重要领域。形式语言:定义为一个严格的数学系统,其严格的形式性使我们能给出形式语言的数学描述,进而揭示所描述语言的结构、特性及其应用范围。描述形式语言有两种方法:生成法识别法。生成法:用文法给出产生该语言的所有句子的规则。根据这些规则可以产生语言中每个句子。这些规则就叫生成式或产生式。例如,下

5、边是个描述“十进制数”的文法:G=({F,I,D,N},{.,0,1,2,3,4,5,6,7,8,9},P,F)令F——“十进制数”、I——“无符号整数”、D——“十进制小数”、N——“数字”于是该文法的产生式集合P中产生式如下:F→I

6、D

7、IDI→N

8、NID→.IN→0

9、1

10、2

11、3

12、4

13、5

14、6

15、7

16、8

17、9例如利用此文法产生3.14:FIDNDN.I3.I3.NI3.1I3.1N3.14识别法:核心是一个自动机。对于给定的符号串可以由自动机识别出是否为给定语言中合法的句子。自动机的具体的例子以后再介绍。1-1形式语言基本概念形

18、式语言必须规定所用基本符号集合,这就是字母表。一.字母表字母表:符号的有限集合。通常用V或者表示。例如V=a,b,c。二.符号串符号串:是由字母表中的符号组成的序列。例如,aabbcc就是上述字母表V上的一个符号串。符号串的长度:即是符号串所含符号个数。例如符号串=aabbcc用表示的长度,则

19、=6。空符号串:不含任何符号的符号串,通常用表示。显然=0。三.符号串的“连接”运算“◦”例符号串x=abc,y=cba,x与y的连接构成符号串z,则z=x◦y=abc◦cba=abccba显然连接运算“◦”满足可结合性且有

20、幺元,即对任何符号串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=Am

21、n当两个集合中有一个集合是空集时,则它们的乘积为空集。即A=A=。五.字母表的闭包V与V*令V是个字母表。则V——由V中符号构成的长度为1的符号串的集合。V

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。