形式语言与自动机理论精品文稿.ppt

《形式语言与自动机理论精品文稿.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机理论精品文稿.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言与自动机理论第1 页，本讲稿共10 页信息与计算科学专业信息与计算科学专业 培养 解决信息技术中所涉及的数学问题的高级人才。信息技术：信息的获取、传输和处理。信息获取：统计、遥感。信息传输：通信、Internet 主要的问题：可靠性、有效性与安全性。数学理论：信息论、编码理论、密码学。信息处理：计算技术，包括数值计算、符号计算、数据挖掘、计算模拟等技术。应用广泛，如：银行金融风险的控制、产品设计、天气预报、密码破译。第2 页，本讲稿共10 页计算理论与技术 本专业的主要目标：掌握计算理论与技术；能够为各种实际问题设计算法，并用计算机求解。主要工作：（1）建模，（2）算法设计与分析。课程

2、体系：1.数学基础，离散数学，概论与统计，数值计算，运筹与优化，数学建模。2.计算理论，数据结构，算法设计与分析。3.程序语言。4.数学建模，算法设计与编程训练。第3 页，本讲稿共10 页理论计算机科学 研究计算理论与技术，是关于计算技术的数学理论。核心理论：（1）形式语言与自动机理论，（2）可计算性理论，（3）计算复杂性理论。其中，形式语言与自动机理论是基础，是本课程的学习内容，包括如下3部分：（1）正规语言与有限自动机，（2）上下文无关语言与下推自动机，（3）图灵机与可判定性理论。第4 页，本讲稿共10 页理论渊源 形式语言理论是美国语言学家乔姆斯基开创的。上个世纪50 年代，乔姆斯基研究

3、如何根据语法规则生成一个语言的所有语句，提出了形式化的文法概念与文法推导方法。他提出的方法类似于逻辑推导。同一时期，数学家克林研究如何自动地识别一个语言的所有语句。克林根据神经细胞的启发提出了识别语言的自动机模型。1959 年，乔姆斯基证明了两者是等价的，即文法所生成的语言都是自动机可识别的，反之亦然。这一结果宣告了形式语言与自动机理论的诞生。此后，该理论在计算机科学技术中得到迅速而广泛的应用。例如，用形式化的文法描述高级编程语言的词法和语法；根据自动机设计编译器。第5 页，本讲稿共10 页课程特点 本课程属于专业理论课，主要特点就是形式化，比较抽象，既有严格的理论证明，又有很强的构造性，难度

4、较大。第6 页，本讲稿共10 页学习目的 掌握形式语言与自动机理论的基本知识，为进一步的学习和应用打基础。训练形式化思维。用规范的语言，严谨地描述事物；考虑事物的形式而非内涵。训练计算思维。“建模 问题分析 算法设计 算法分析。”考虑：问题的可计算性与计算复杂性，追求高效率的算法。第7 页，本讲稿共10 页习题与实验 每一讲都布置适量的习题作为课后作业，用于理解、消化所学的知识。不安排实验。理论学习必须做习题。第8 页，本讲稿共10 页考试与成绩评定 开卷笔试 成绩评定 总评成绩=平时20%+期末考试80%。平时成绩=考勤10分+作业10分。全班成绩分布：20%:30%:30%:20%第9 页，本讲稿共10 页教学参考书蒋宗礼、姜守旭编著形式语言与自动机理论（第2版）清华大学出版社，2007。王柏 杨娟编著 形式语言与自动机北京邮电大学出版社，2008。第10 页，本讲稿共10 页