教学目的、要求
本课程为计算机软件与理论专业硕士研究生的专业基础课。 形式语言是研究自然语言和人工语言的数学工具。自动机理论研究抽象计算装置或“机器”。形式语言与自动机理论研究问题的自动化，方法是：将问题分为若干基本问题类，给出了各问题类对应的计算模型，通过研究这些模型的性质及其变化方法来对这些问题进行研究。这种“问题-形式化-自动化”的方法和思想是进行计算机问题求解的基本途径，对于计算机科学与技术工作者是非常重要的。另外，形式语言与自动机理论还是研究算法理论的基础。 本课程重点讲述具有实用意义的正规文法与有限状态自动机、上下文无关文法与下推自动机、同时还介绍具有理论价值的其他几类文法和图灵机，以及计算理论中的不可判定问题和难解问题。通过本课程的学习，希望学生学到计算机科学中的一些最基本的方法和思想，培养学生的计算思维能力，为走向深入和广博打下基础。
预修课程
离散数学
教材
《形式语言与自动机导论》，林兹著，孙家骕译，机械工业出版社，2005年翻译出版。
主要内容
第1章 计算理论导引 1.1 数学预备知识和表示 1.2 三个基本概念 1.3 一些应用 第2章 有穷自动机 2.1 确定型有穷接受器 2.2 非确这型有穷接受器 2.3 确定型有穷接受器和非确定型有穷接受器的等价性 2.4 减少有穷自动机中状态的化简 第3章 正则语言与正则文法 3.1 正则表达式 3.2 正则表达和正则语言之间的联系 3.3 正则文法 第4章 正则语言的性质 4.1 正则语言的封闭性质 4.2 正则语言的基本问题 4.3 识别非正则语言 第5章 上下文无关语言 5.1 上下文无关方法 5.2 分析和二义性 5.3 上下文无关文法和程序设计语言 第6章 上下文无关文法的化简与范式 6.1 文法变换方法 6.2 两个重要的范式 6.3 上下文无关文法的成员资格判定算法 第7章 下推自动机 7.1 非确定型下推自动机 7.2 下推自动机与上下文无关语言 7.3 确定型下推自动机和确定型上下文无关语言 7.4 确定型上下文无关语言的文法 第8章 上下文无关语言的性质 8.1 两个泵引理 8.2 上下文无关语言的封闭性质和判定算法 第9章 图灵机 9.1 标准图灵机 9.2 完成复杂任务的组合图灵机 9.3 图灵论题 第10章 图灵机的其他模型 10.1 对图灵机的等价性 10.2 具有更复杂存储的图灵机 10.3 非确定型图灵机 10.4 通用图灵机 10.5 线性有界自动机 第11章 形式语言和自动机的层次结构 11.1 递归语言和递归可枚举语言 11.2 无限制文法 11.3 上下文相关文法和语言 11.4 乔姆斯基层次结构 第12章 算法计算的限制 12.1 图灵机所不能解决的问题 12.2 递归可枚举语言的不可判定问题 12.3 波斯特对应问题 12.4 上下文无关语言的不可判定问题