计算理论课件第一章

(31页)

'计算理论课件第一章'
计算理论基础 信息科学与工程学院计算机软件与理论研究所 许桂清 杨莹 序 言一. 本课的性质以及研究的内容? 任何一门学科都有它的基础和它的基本问题,如物质 的本质是什么?有机体生命的基础和起源是什么?? 什么是计算机科学的基础?什么是计算机科学的基本 问题? 诸如什么是形式语言?什么是计算?什么是能计算的? 什么是不能计算的?什么是算法?如何评价算法?什 么样的算法是可行的?这些问题能否判定?这又引出 什么是可判定的?什么是不可判定的?? 这些问题就是计算理论要讨论的问题。性质:该课是计算机科学的理论课。? 计算理论:就是研究理论计算机的科学。? 理论计算机:是研究计算机的理论模型,研究计算机的本质,也就是把计算机看成一个数学系统。(因为计算机科学的基本思想和模型在本质上是数学——离散的。)内容:? 形式语言与自动机理论: 正规文法与有限自动机(正规语言) 、 上下文无关文法与下推自动机(上下文无关语言) 图灵机(递归可枚举语言)? 可计算性理论: 什么是可计算?? 计算复杂性理论: 时间复杂性 、 空间复杂性。? 递归函数二. 学习目的:? 了解这些计算理论 我们知道计算机不论从它的诞生还是它的快速发展过程都没有离开计算理论,也就是它是在计算理论指导下诞生和发展的。并课所涉及的都是计算机科学的基本问题。不首先了解它们,是很难理解计算机科学的。作为计算机科学与技术专业的本科生和研究生应该了解这些计算理论。? 培养能力 此外此课可以培养学生抽象逻辑思维和形式化思维的能力。? 为学习《编译原理》做准备 第一章形式语言概述 语言是人们交流思想的工具。按照语言的形成,可将语言分成二类:自然语言和人工语言(形式语言)。一. 自然语言 如汉语、英语、法语、日语等等都是自然语言。 形成:是大多数人经过长期地社会实践逐渐形成的。 特点:种类繁多,内容丰富,表达能力强。 缺点:具有地方性,不便互相交流。有时不够精确,有多义性。比如汉语中的“打”字,具有多种解释。如 打伞、打扑克、打醋、打人、一打袜子等等。因此自然语言不适合计算机的程序设计语言。二.形式语言 如计算机的各种程序设计语言、数理逻辑中的谓词演算语言等都属于形式语言。 形成:是少数人经过严格地形式定义确定的语言。 特点:定义准确,无歧义性。 在五十年代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|ID F?ID?ND I→N|NI ?N.I?3.I D→.I N→0|1|2|3|4|5|6|7|8|9 ?3.NI?3.1I例如利用此文法产生3.14: ?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=x2 x? x? x=x3一般地 xn-1? x=xn xm? 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=A2 AmAn= 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∈L,则称w是L中的一个句子。例如,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|ID I→N|NI D→.I N→0|1|2|3|4|5|6|7|8|9可见一个文法中有两种符号。 非终极符1.文法( Grammar)定义一个文法G是个有序四元组,记作 G=(VN,VT ,P,S),其中 VN ?非终极符(变元)集合,用大写英文字母表示。 VT ?终极符集合。 ∪ 这里VN ∩VT =Ф。有时记作 VN VT=V P?生成式(也叫产生式)的集合。 产生式的形式: α→β,其中 α∈V?,β∈V * α→β的含义是:可以用符号串β代替符号串α。 另外如果有α→β,α→γ,α→δ 可简记成α→β|γ|δ ∈ S?开始变元,S VN 。【例1-2.1】下面是定义只含有+和*运算的算术表达式的文法。 G1=(VN ,VT ,P,E) VN={E,T,F}, VT={a,b,+,*,(,)} P={E→E+T, E→T, T→T*F, T→F, F→(E), F→a, F→b}【例1-2.2】 G2=({S},{0,1},P,S) P={S→0S1|01}文法中使用的符号通常作如下约定:(1)用大写英文字母表示变元。S通常表示开始变元。(2)用小写的a,b,c,…表示终极符。 ∈ *(3)用x,y,z,…表示终极符串,即x,y,z,… VT 。(4)用α,β,γ,…希腊字母表示既含有终极符,也含有 ∈ ∪ *非终极符的符号串,即α,β,γ,… (VN VT) 。2.句型(Sentential form) 设文法 G =(VN,VT ,P,S),则(1)S是个句型。(2)若αβγ是个句型,且β→δ是P中的一个产生式,则αδγ也是一个句型。 按此定义,对于文法G2来说, P={S→0S1|01} S,0S1,00S11,000111都是句型。3.句型的推导(派生) 设文法G=(VN ,VT ,P,S),若αβγ是G的一个句型,且β→δ∈P,则αδγ也是一个句型,我们就称为可由句型αβγ直接推导出αδγ,记作αβγ?Gαδγ。如果没有其它文法,不会产生混淆的情况下,此推导可简记成αβγ?αδγ。 符号“?”表示句型之间的直接推导(派生)关系。 如果有α1?α2?α3?…?αn ,则表示由α1可以间 *接推导出αn ,可以写成α1 ? αn , 符号“?*”表示句型之间经过多步间接推导的关系。 符号“?k”表示句型之间经过k步间接推导的关系。4. 文法产生的语言 设文法 G =(VN,VT,P,S),令集合 ∈ * * L(G)={w|w V
关 键 词:
计算理论课件第一章 ppt、pptx格式 免费阅读 下载 天天文库
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:计算理论课件第一章
链接地址: https://www.wenku365.com/p-42277312.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开