加入收藏 | 设为首页 | 搜索
计算机学院( 国家示范性软件学院 )简介
北京邮电大学1977年开设计算机通信本科专业,1985年成立计算机工程系,1998年成立计算机科学与技术学院。2008年,按照“学科归位”的原则,将计算机科学与技术学院等六个单位计算机学科的资源重新整合为计算机学院。2020年,将原计算机学院、软件学院、网络技术研究院调整、合并组建新的计算机学院(国家示范性软件学院),并支撑网络与交换技术国家重点实验室(北京邮电大学)。
课程信息
形式语言与自动机
课程编号  512.5*080
课程名称  形式语言与自动机
任课老师          王柏  石川  
课程类型  必修/学位课
课程阶段  硕士
学时学分  36学时2学分
基本要求  通过本课程学习,要求学生掌握形式化描述方法,建立起形式语言、自动机模型以及形式语言与自动机的关系等概念,并通过一些定理的证明和应用,对学生进行形式化思维训练,提高用数学工具对问题进行抽象建模的能力,培养学生清晰而准确地表达问题的能力。
内容提要    
第一章  绪论
第二章  语言与文法
1. 形式语言概念
2. Chomsky文法体系
第三章  有限自动机和有限性文法
1. 确定的有限自动机(DFA)
2. 不确定的有限自动机(NFA)
3. NFA与DFA的等效变换
4. 有e转换的NFA
5. 正则式与有限自动机
6. 右线性语言的性质
7. 双向有限自动机与有输出的有限自动机
第四章  上下文无关方法与下推自动机
1. 推导树与二义性;
2. 上下文无关文法的变换及算法
3. Chomshy范式与Greibach范式
4. 上下文无关文法与下推自动机的等效性
5. 上下文无关文法的性质
第五章  图灵机
1. 基本图灵机
2. 图灵机的构造技术
3. 受限型图灵机与基本图灵机的等效;
4. 无限制文法与图灵机
第六章 翻译原理   
1. 翻译式
2. 转换器
3. 词法分析
4. 句法分析      
第七章 自动机理论在通信领域的应用  
1. 状态机模型的局限性
2. MSC和SDL简介
教学方式  
指定教材  
参考书目  1. 王柏 杨娟 编著:《形式语言与自动机》  北京邮电大学出版社,2003年版
2. 美J.D.霍普克罗夫特等:《自动机理论、语言和计算导引》, 科学出版社1990
3. 美 Michael Sipser 著,张立昂 等译:《计算理论导引》,机械工业出版社,2000
4. 蒋宗礼 姜守旭:《形式语言与自动机理论》,清华大学出版社 2003
5. 美A.V. 阿霍 等:《形式语言及其句法分析》,科学出版社1987
先修课程  计算机导论与程序设计、数据结构、离散数学
开课学期  秋
更多内容