形式语言与自动机课程教学大纲课程基本信息中文名称形式.pdfVIP

形式语言与自动机课程教学大纲课程基本信息中文名称形式.pdf

  1. 1、本文档共3页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多

形式语言与自动机课程教学大纲课程基本信息中文名称形式

《形式语言与自动机》课程教学大纲

一、课程基本信息

中文名称:形式语言与有限自动机

英文名称:FormalLanguagesandAutomataTheory

开课学院:计算机科学学院课程编码:S0812301

学分:2总学时:36

适用专业:计算机科学与技术学术硕士

修读基础:《离散数学》,《数字逻辑》

课程负责人:陈伟(教授)

主讲教师:陈伟(教授)

二、课程目的任务

1.课程地位作用(课程在实现培养目标中的地位作用)

《形式语言与自动机》是计算机科学的理论基础,本课程主要目

的在于利用有限自动机与正则表达式的等价关系,通过表达式描述问

题,利用不同有限自动机类型实现解决方案,通过更一般化的上下文

无关文法描述,利用下推自动机实现问题求解,培养学生描述问题、

分析问题、寻求对策的创新思维模式,提高知识综合应用能力。

2.课程主要内容(简述:主要内容、重点、难点等)

主要内容包括:自动机理论发展历史、有限自动机的描述特点与

工作方式(重点、难点)、正则表达式与语言(重点、难点)、正则

语言性质、上下文无关文法与语言(重点、难点)、下推自动机、上

下文无关语言的性质(重点、难点)等。

3.学生应达到的基本要求

本课程基本要求在于掌握有限自动机类型,有限自动机与正则表

达式的等价关系、正则文法性质、上下文无关文法与范式、下推自动

机与上下文无关语言性质,重点在于研究应用方法。

三、教学内容与学时分配

(一)自动机:方法与体验(2学时)

主要内容:

为什么研究自动机理论,自动机理论发展历史,预备知识:字母

表、串、语言、问题,主要命题证明方式。

重点:预备知识

(二)有限自动机(6学时)

主要内容:

有限自动机的非形式化描述,确定型有限自动机、非确定型有限

自动机、含空转移有限自动机的描述特点与工作方式,三类自动机的

等价转换方式,子集构造、空闭包概念,自动机的应用。

重点:有限自动机的描述特点与工作方式

(三)正则表达式与语言(6学时)

主要内容:

正则表达式的定义,自动机FA与正则式RE的等价性及效验,RE

代数规则及测试正则式RE的应用。

重点:自动机FA与正则式RE的等价性

(四)正则语言性质(6学时)

主要内容:

证明语言的非正则性,泵引理,正则语言的闭合性(闭合算子),

正则语言的判定性(测试正则语言的空或成员)、自动机的状态等价

与自动机最小化。

重点:正则语言的闭合性与自动机最小化

(五)上下文无关文法与语言(6学时)

主要内容:

上下文无关文法的定义,文法推导过程,上下文无关文法的语言,

语法分析树和推导的等价性,语法分析器及其它上下文无关文法应用,

语法和语言中的歧义性及消除方法。

重点:语法分析树和推导的等价性

(六)下推自动机(6学时)

主要内容:

下推自动机的定义,下推自动机的语言,下推自动机与上下文无

关文法的等价性,确定型下推自动机定义与正则语言。

重点:下推自动机的工作方式与应用

(七)上下文无关语言的性质(4学时)

主要内容:

上下文无关文法的范式,上下文无关语言的泵引理,上下文无关

语言的闭合性,上下文无关语言的判定性。

重点:上下文无关语言的闭合性

四、考核方式与成绩评定

1.考核方式:(笔试、论文、口试等)

要求平时认真听课,完成四则运算计算器表达式的文法描述及解

释执行的大作业。

2.成绩评定办法:(平时成绩、期末考试成绩……等比例)

论文撰写(70%)

专题讨论和答辩(30%)

五、教材及主要参考书目

(一)教材

[1]JohnE.Hopcroft,RajeevMotwaniandJeffreyD.Ullman,

IntroductiontoAutomataTheory,LanguagesandComputatio

您可能关注的文档

文档评论(0)

135****5548 + 关注
官方认证
文档贡献者

各类考试卷、真题卷

认证主体社旗县兴中文具店(个体工商户)
IP属地河南
统一社会信用代码/组织机构代码
92411327MAD627N96D

1亿VIP精品文档

相关文档