- 1、本文档共3页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 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
您可能关注的文档
- 接触网技术规范.pdf
- 2023年安全知识竞赛活动方案_5.pdf
- 每日工作实习日志【7篇】.pdf
- 2022年四级英语完形填空答案加翻译.pdf
- 油画表现语言智慧树知到答案章节测试2023年齐鲁师范学院.pdf
- 【工程监理】管道试压试验的监控要点.pdf
- 建筑给排水工程设计开题报告.pdf
- 山东工艺美术学院《大学英语》2018-2019学年期末试卷.pdf
- 学校开展科技教育活动总结(3篇).pdf
- 西南11J合订本(1)-11J201_原创精品文档.pdf
- 白天晚上教学课件.ppt
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题参考答案详解.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题带答案详解.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题及参考答案详解.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题及参考答案详解一套.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题及完整答案详解1套.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题及参考答案详解1套.docx
- 2025年山东菏泽市事业单位招聘急需紧缺岗位目录(第一批)笔试模拟试题参考答案详解.docx
- 2025年山东菏泽市牡丹区中医医院引进急需紧缺专业技术人才30人笔试模拟试题及答案详解1套.docx
- 画西瓜教学课件.ppt
最近下载
- JB-T7752-2005_滚动轴承密封深沟球轴承技术条件.pdf VIP
- 装配式混凝土结构部品部件吊装监理实施细则(标准化格式文本).doc VIP
- 萧山区地图杭州市萧山区乡镇街道地图高清矢量可填充编辑地图PPT模板.pptx
- 全国初中物理竞赛试题专项(力)精编(2024版)(附答案).pdf VIP
- 人教版七年级数学上册试题 第6章 几何图形初步 章节检测卷 (含详解).docx VIP
- 装配式混凝土结构施工监理实施细则(标准化格式).doc VIP
- 绿色智能船舶制造基地项目可行性研究报告.pptx VIP
- 船舶制造基地可行性研究报告.doc VIP
- 第八节 伏安法测电动势内阻-2024-2025学年高二上学期物理专项训练.pdf VIP
- 节能分部工程监理研究细则.doc VIP
文档评论(0)