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

形式语言与自动机理论第1页，本讲稿共10页信息与计算科学专业培养 解决信息技术中所涉及的数学问题的高级人才。信息技术：信息的获取、传输和处理。信息获取：统计、遥感。信息传输：通信、Internet 主要的问题：可靠性、有效性与安全性。数学理论：信息论、编码理论、密码学。信息处理：计算技术，包括数值计算、符号计算、数据挖掘、计算模拟等技术。应用广泛，如：银行金融风险的控制、产品设计、天气预报、密码破译。第2页，本讲稿共10页计算理论与技术本专业的主要目标：掌握计算理论与技术；能够为各种实际问题设计算法，并用计算机求解。主要工作：（1）建模，（2）算法设计与分析。课程体系：1.数学基础，离散数学，概论与统计，数值计算，运筹与优化，数学建模。2.计算理论，数据结构，算法设计与分析。3.程序语言。4.数学建模，算法设计与编程训练。第3页，本讲稿共10页理论计算机科学研究计算理论与技术，是关于计算技术的数学理论。核心理论：（1）形式语言与自动机理论，（2）可计算性理论，（3）计算复杂性理论。其中，形式语言与自动机理论是基础，是本课程的学习内容，包括如下3部分：（1）正规语言与有限自动机，（2）上下文无关语言与下推自动机，（3）图灵机与可判定性理论。第4页，本讲稿共10页理论渊源形式语言理论是美国语言学家乔姆斯基开创的。上个世纪50年代，乔姆斯基研究如何根据语法规则生成一个语言的所有语句，提出了形式化的文法概念与文法推导方法。他提出的方法类似于逻辑推导。同一时期，数学家克林研究如何自动地识别一个语言的所有语句。克林根据神经细胞的启发提出了识别语言的自动机模型。1959年，乔姆斯基证明了两者是等价的，即文法所生成的语言都是自动机可识别的，反之亦然。这一结果宣告了形式语言与自动机理论的诞生。此后，该理论在计算机科学技术中得到迅速而广泛的应用。例如，用形式化的文法描述高级编程语言的词法和语法；根据自动机设计编译器。第5页，本讲稿共10页课程特点本课程属于专业理论课，主要特点就是形式化，比较抽象，既有严格的理论证明，又有很强的构造性，难度较大。第6页，本讲稿共10页学习目的掌握形式语言与自动机理论的基本知识，为进一步的学习和应用打基础。训练形式化思维。用规范的语言，严谨地描述事物；考虑事物的形式而非内涵。训练计算思维。“建模 问题分析 算法设计 算法分析。”考虑：问题的可计算性与计算复杂性，追求高效率的算法。第7页，本讲稿共10页习题与实验每一讲都布置适量的习题作为课后作业，用于理解、消化所学的知识。不安排实验。理论学习必须做习题。第8页，本讲稿共10页考试与成绩评定开卷笔试成绩评定 总评成绩=平时20%+期末考试80%。平时成绩=考勤10分+作业10分。全班成绩分布：20%:30%:30%:20%第9页，本讲稿共10页教学参考书教学参考书蒋宗礼、姜守旭编著形式语言与自动机理论（第2版）清华大学出版社，2007。王柏 杨娟编著 形式语言与自动机北京邮电大学出版社，2008。第10页，本讲稿共10页