一起文库网 懒人学习网 雨竹林中考网 高考报名网 雨竹林文档网 加入收藏 设为首页

雨竹林文档网      懒人考试网|阳光学习网


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

一起文库网   来源: 形式语言与自动机  2024-01-22     

本站非官方网站,信息完全免费,仅供参考,不收取任何费用,具体请以官网公布为准!
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

懒人学习网   学习文档   news.lazyedu.cn : 懒人学习网,免费分享学习资料。

[责任编辑:文库在线]

懒人学习百事通懒人学习网 懒人考试网

学参学习网,非官方公益学习阅读网!

非官方网站: 本站为网址导航站点,非官方网站,具体以官方网站公布为准.

公益免费: 本站所有信息完全免费,不收取任何费用,谨防上当受骗.

信息仅供参考: 因信息具有时效性,本站所有信息仅供参考,请勿用于非法用途.


郑重声明:本站不开设任何辅导班,谨防上当受骗!完全公益站点,不接受任何赞助!



免费阅读

新免费分享的文档

本站所有信息完全免费,不收取任何费用!

使用必读 |   学习文库 |   阳光学习网 |   一起学习吧 |   懒人考试网 |   郑重声明 |   懒人考试网 | 雨竹林文档网

(C) 懒人学习网  学参网手机版  高考网   版权所有

非官方公益学习网,本站不开设任何辅导班、不收取任何费用!闽ICP备11025842号-4 | 打着本站名义收费的均为冒充的骗子!

Copyright XUECAN, All Rights Reserved.