Lec 13-15: 语言分析、有限状态自动机、图灵机¶
1. 形式语言 (Formal Language)¶
1.1 基本概念¶
- 字母表 (alphabet) \(A\)：非空有穷符号集
- 字符串/字 (string/word)：字母表中符号组成的有穷序列
- 空串 (empty string) \(\varepsilon\)：长度为 0 的字符串
- 语言 (language) \(L\)：\(A^*\) 的子集（\(A^*\) 是 \(A\) 上所有字符串的集合）
1.2 乔姆斯基谱系 (Chomsky Hierarchy)¶
| 类型 | 名称 | 产生式形式 |
|---|---|---|
| 0 型 | 无限制文法 | \(\alpha \to \beta\) |
| 1 型 | 上下文有关文法 | \(\alpha A \beta \to \alpha \gamma \beta\) |
| 2 型 | 上下文无关文法 | \(A \to \gamma\) |
| 3 型 | 正则文法 | \(A \to aB\) 或 \(A \to a\) |
2. 有限状态自动机 (Finite State Automaton)¶
2.1 定义¶
有限状态机 \(M(A,S,Y,s_0,F)\)： - \(A\)：输入字母表 - \(S\)：有穷状态集 - \(Y \subseteq S\)：接受状态集 - \(s_0 \in S\)：初始状态 - \(F: S \times A \to S\)：状态转移函数
2.2 状态转移图¶
用有向图表示自动机： - 顶点 = 状态 - 边 = 状态转移，标注输入符号 - 双圈 = 接受状态 - 箭头指向初始状态
2.3 正则语言 (Regular Language)¶
- Kleene 定理：语言 \(L\) 是正则的 \(\leftrightarrow\) 存在有限状态机 \(M\) 使得 \(L = L(M)\)
- 泵引理 (Pumping Lemma)：所有长度超过状态数目的接受串 \(w\) 都可以表示为 \(w = xyz\)，且 \(xy^mz\) 都会被 \(M\) 接受
2.4 机器化简¶
机器同余 (machine congruence)：状态集上的等价关系 \(R\)，满足 \(\forall s,t \in S\)，若 \(sRt\)，则对于所有输入 \(x\)，有 \(F(x,s)RF(x,t)\)
商机器 (quotient machine) \(M/R\)：将等价的状态合并后得到的简化机器
3. 图灵机 (Turing Machine)¶
3.1 基本构造¶
- 一条无限长的纸带，每格可容纳一个字符
- 一个读写头，可以在纸带上移动
- 一系列关于读写头动作的规则
3.2 形式化定义¶
状态转移函数：\(\delta: Q \times \Gamma \to Q \times \Gamma \times \{L,R,N\}\)
每条规则为五元组 \(q = \langle s_i, a_k, s_j, a_l, d \rangle\)： - \(s_i, s_j \in S\)：内部状态 - \(a_k, a_l \in A\)：纸带字符 - \(d \in \{L,R,N\}\)：左移、右移、不动
3.3 识别、枚举与判定¶
| 概念 | 说明 |
|---|---|
| 识别 | 属于语言的串在有限步被接受；否则被拒绝或永不停机 |
| 枚举 | 生成所有属于语言的串（可能永不停止） |
| 判定 | 属于语言的串被接受；否则被拒绝（必停机） |
定理：可识别 = 可枚举
3.4 停机问题 (Halting Problem)¶
- 停机问题是不可计算的
- 不存在一个通用算法能判断任意程序是否会停止
4. 哥德尔不完备定理¶
4.1 哥德尔编码¶
设 \(p(n)\) 为第 \(n\) 个素数，\(L \subseteq A^*\)，\(A = \{a_1,a_2,\ldots,a_n\}\)，任意 \(w = a_{m_1}a_{m_2}\ldots a_{m_k} \in L\)：
4.2 通用图灵机¶
存在通用图灵机 \(U\)，接受两个输入 \(a,k\)（其中 \(a\) 是图灵机的哥德尔数，\(k\) 是输入的哥德尔数），模拟 \(M(a)\) 在输入 \(I(k)\) 下的计算。
4.3 不完备定理¶
任何包含自然数定义的形式系统都是不完全的——存在既不能证明为真、也不能证明为假的命题。