首页 > 句子qq红包外挂秒抢 > 爱情语言 > 《形式语言与自动机》教学大纲

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

时间:2019-04-23???来源:爱情语言???点击:
063403 ??? 形式语言与自动机???????????????? ???????????? 32学时/ 2学分
英文译名:Formal Language and Automata
适用领域:计算机软件与理论、计算机应用技术
开课单位:计算机科学与技术学院
教学目的:形式语言和自动机理论是理论计算机科学的重要分支,在计算机科学的许多领域起着理论基础和方法论的作用,特别是对程序语言的设计、编译理论与技术、模型检测、模式识别和自然语言理解等领域起了重要促进作用。通过对本课程的学习,研究生能够从文法和识别器的角度,掌握各类文法和自动机设计的方法和技术,提高问题的形式化描述和抽象思维能力,理解并实践“问题、形式化描述、自动化(计算机化)”的解决问题过程。
预备知识或先修课程要求:离散数学或相关知识。
教学方式及学时分配:课堂授课32学时。
?
学时 教学内容 教学方式 2 课程概述、语言和句子的概念 授课 2 文法的形式定义、文法的构造 授课 2 文法的乔姆斯基体系、空句子 授课 2 语言的识别、有穷状态自动机 授课 2 不确定的有穷状态自动机、带空移动的有穷状态自动机 授课 2 FA是正则语言的识别器、FA的变形 授课 2 正则表达式 授课 2 正则语言等价模型的总结、正则语言的性质 授课 2 正则语言的泵引理、正则语言的封闭性 授课 2 Myhill-Nerode定理与DFA的极小化 授课 2 关于正则语言的判定算法、上下文无关文法及化简 授课 2 乔姆斯基范式、格雷巴赫方式、自嵌套文法 授课 2 下推自动机的基本定义、PDA与CFG等价 授课 2 上下文无关语言的性质、泵引理和封闭性 授课 2 上下文无关语言的判定算法、图灵机的基本概念 授课 2 图灵机的变形、几个相关的概念、课程总结 授课 ? ?
教学主要内容以及对学生的要求:
教学主要内容是形式语言与自动机方面的主要理论成果和应用实例。
要求研究生系统地掌握各类文法和自动机设计的方法和技术,形成问题的形式化描述和抽象思维的能力。
内容摘要:教学内容以四类形式语言和相应的自动机为主线,讨论形式语言与自动机方面的主要理论成果和应用实例。主要包括:介绍形式语言及其相关概念,按乔姆斯基体系讨论四类形式文法。详细介绍有穷自动机的概念、各种变形及其应用;介绍正则表达式的概念,讨论各种等价变换方法,并论述正则表达式和有穷自动机的关系;对正则语言的各种表现形式加以总结,论述正则语言的各种重要性质,并重点讨论有穷自动机的极小化问题。介绍上下文无关文法的基本概念和性质,引入下推自动机的概念,并论证下推自动机和上下文无关文法的等价性。介绍图灵机的基本概念,给出它的基本模型和各种变形,用实例表明图灵机具有很强的识别能力和计算能力,并说明图灵机和0型文法的等价性。简单介绍线性有界自动机,并证明它与上下文有关文法等价性。对各语言类之间的关系做一总结。
考核方式:闭卷考试,平时作业等占一定比例(不超过30%)。
课程主要教材:形式语言与自动机理论(第2版) .蒋宗礼.清华大学出版社,2007
主要参考书目:
[1] 自动机理论、语言和计算导论(原书第3版).(美)霍普克罗夫特着.机械工业出版社,2008
[2] 计算理论导引(第2版) .(美)西普塞.机械工业出版社,2006
[3] 形式语言与自动机. 陈有祺.机械工业出版社,2008
推荐访问:形式语言与自动机答案

热门文章

?