一、语言
1. 描述语言需要有穷表示
因为，有穷语言可以通过枚举该语言的所有字符串来表示，所以，有穷语言是可以有穷表示的。
对于无穷语言，则需要考虑了。一方面，有穷表示都是字符串，所以有穷表示的集合是字符串集合。字符串集合中的元素数目是可数无穷的，这样，有穷表示是可数无穷的。另一方面，语言是字符串集合的子集，所以，语言的集合是字符串集合的幂集。根据对角化方法，可以证明语言的种类是不可数无穷的。因此，结论是，我们只有可数个表示，却有不可数个语言，不可能有穷地表示所有的语言。
2. 语言的表示方式称为文法
不同文法的表达能力是不一样的。如果文法F能够描述文法G能够描述的所有语言，并且还能够描述文法G不能描述的语言，那么，我们称文法F比文法G的表达能力更强。
根据表达能力从弱到强的顺序，有正则文法、上下文无关文法和Turing机。
3. 语言的表示方式有两种
包括语言生成器和语言识别器。其中，语言识别器是算法性质的。正则文法对应于有穷自动机；上下文无关文法对应于下推自动机；
二、正则语言
1. 正则表达式（Regular Expression, RE）
字母表∑上的正则表达式是字母表∑∪｛(，)，⊙，∪，★｝上通过如下规则获得的所有字符串：
- ∑或⊙中的成员，是RE
- 如果α和β是RE，则(αβ)也是RE
- 如果α和β是RE，则(α∪β)也是RE
- 如果α是RE，则α★也是RE
换言之，RE是关于连接、并和Kleene星号运算闭包的。
2. 正则语言(Regular Language, RL)
一个RE可以表示一个语言，从RE到语言的映射可以由函数L来定义。函数L的定义如下：
- L(⊙) = ⊙
- 任意a∈∑，L(a) = {a}
- 如果α和β是RE，则L(αβ) = L(α)L(β)
- 如果α和β是RE，则L(α∪β)= L(α)∪L(β)
- 如果α是RE，则L(α★) = (L(α))★
如果L= L(α)，其中α是字母表∑上的任一正则表达式，则称L是一个正则语言。
3. 确定型有穷自动机(Definite Finite Automata, DFA)
DFA是一个五元组M = (K, ∑, δ, s, F)，其中
- K是有穷的状态集合
- ∑是字母表
- s∈K是初始状态
- F≤K是终结状态的集合
- δ是类型为K×∑->K的函数，称为转移函数
M的格局是K×∑★的任一元素。如果(q,ω)和(q’,ω’)是M的两个格局，并且对于某个符号a∈∑，有ω= aω’且δ(q, a)=q’，则称M从格局(q,ω)经过一步可以到达格局(q’,ω’)。如果M可以从格局(s,ω)经过有限步到达格局(q,ε)，其中q∈F，那么，称字符串ω被M接受。M接受的语言是M接受的所有字符串的集合，记作L(M)。
4. 非确定型有穷自动机(NonDefinite Finite Automata, NDFA)
NDFA是一个五元组M = (K, ∑, δ, s, F)，其中
- K是有穷的状态集合
- ∑是字母表
- s∈K是初始状态
- F≤K是终结状态的集合
- △是类型为K×(∑∪{ε})×K的关系，称为转移关系
M的格局，格局间的到达关系以及L(M)的定义与DFA类似。但是，对于DFA来说，到达关系是一个函数；对于NDFA来说，则不是函数。
5. 定理
(1) 对于每一台NDFA，都可以构造一台等价的FA。
(2) 一个语言是正则的当且仅当它被FA接受。
(3) 正则语言类在并、交、连接、Kleene星号和补运算下是封闭的。
(4) (RL泵引理) L 是一个正则语言。必定存在一个常数 n (依赖于L)，对 L 中的任何串ω，如果 |ω|≥n， 则可以把 ω 分成三个段 ω=xyz, 使得
a) y ≠ε
b) |xy|≤n
c) 对任意 k>=0, xykz 也在 L 中.
(5) 有一个指数算法，给定一个NDFA，构造一个等价的DFA。
(6) 有一个指数算法，给定一个NDFA，构造一个等价的RE。
(7) 有一个指数算法，给定两个NDFA（或RE），判断它们是否等价。
(8) 有一个多项式算法，给定一个RE，构造一个等价的NDFA。
(9) 有一个多项式算法，给定一个DFA，构造一个等价的状态最少的DFA。
(10) 有一个多项式算法，给定两个DFA，判断它们是否等价。
(11) 如果L是一个RL，则有一个算法，任给ω∈∑★，它在Θ(|ω|)时间内检查ω是否在L中。
(12) 如果M = (K, ∑, δ, s, F)是一个NDFA，则有一个算法，任给ω∈∑★，它在Θ(|K|2|ω|)时间内检查ω是否在L(M)中。