Part I: Introduction  Chapter 0: Preliminaries  Chapter 1: Language and Computation Part II: Models  Chapter 2: Finite Automata  Chapter 3: Regular Expressions  Chapter 4: Context-Free Grammars  Chapter 5: Pushdown Automata  Chapter 6: Turing Machines

形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析

The halting problem is undecidable Decidability

南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Petri Net

Turing Machines Recursive and Recursively Enumerable Languages

Statement Applications

Formalism Derivations Backus-Naur Form Left- and Rightmost Derivations

2.1 例子语言 2.2 文法和语言的关系 语言的定义 文法的定义 文法与语言的关系 2.3 Chomsky对文法、语言分类 2.4文法产生语言 2.5 无用非终结符 2.6 推导树 2.7 空串定理（自学） 2.8 消除左递归 2.10 语言之间的运算及运算封闭性 2.11 正则表达式和正则集

对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论。集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务

一、程序设计语言的发展 二、形式语言与自动机 三、形式语义学 四、程序设计方法学 五、计算语言学 六、软件开发方法学