CS Wiki

第13章 计算建模 — 章节汇总

11分钟阅读

第13章 计算建模 — 章节汇总

概览

第13章是离散数学的收官之章，系统介绍了计算建模（Modeling Computation）的理论基础。全章从形式语言和文法的数学定义出发（13.1），建立描述语言的形式化工具；然后引入有限状态机（Finite-State Machine）作为最简单的计算模型——先介绍带输出的 Mealy 机和 Moore 机（13.2），再介绍不带输出的 DFA 和 NFA（13.3）；接着讨论正则语言和正则表达式，通过 Kleene 定理建立正则语言与有限自动机的等价关系（13.4）；最后以图灵机（Turing Machine）作为通用计算模型的终极形式，引入 Church-Turing 论题和停机问题的不可判定性（13.5）。全章体现了从”语言描述→简单计算模型→复杂度层次→通用计算模型”的递进知识链条，将离散数学的各个分支（逻辑、集合、关系、算法、图论、布尔代数）统一在”什么是可计算性”这一根本问题之下。

全章知识框架

graph TB
    A["第13章 计算建模"] --> B["13.1 语言与文法"]
    A --> C["13.2 带输出的有限状态机"]
    A --> D["13.3 不带输出的有限状态机"]
    A --> E["13.4 语言识别"]
    A --> F["13.5 图灵机"]

    B --> B1["字母表与字符串"]
    B --> B2["形式语言"]
    B --> B3["文法四元组 G=(V,T,S,P)"]
    B --> B4["派生与派生树"]
    B --> B5["乔姆斯基文法分类 0/1/2/3型"]
    B --> B6["BNF 记法"]

    C --> C1["FSM 六元组"]
    C --> C2["Mealy 机（输出与转移关联）"]
    C --> C3["Moore 机（输出与状态关联）"]
    C --> C4["状态转移表/图"]

    D --> D1["DFA 五元组"]
    D --> D2["扩展转移函数"]
    D --> D3["NFA"]
    D --> D4["NFA-DFA 等价（子集构造法）"]

    E --> E1["正则表达式递归定义"]
    E --> E2["等价变换恒等式"]
    E --> E3["Kleene 定理"]
    E --> E4["泵引理"]
    E --> E5["下推自动机"]

    F --> F1["图灵机七元组"]
    F --> F2["读写头与无限带"]
    F --> F3["函数计算与语言识别"]
    F --> F4["Church-Turing 论题"]
    F --> F5["停机问题不可判定"]
    F --> F6["P/NP 与计算复杂性"]

    B -.->|"文法描述语言"| D
    C -.->|"去掉输出"| D
    D -.->|"正则语言等价"| E
    E -.->|"超越正则语言"| F
    D -.->|"增加带和读写头"| F

    style A fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style B fill:#fff3e0,stroke:#e65100
    style C fill:#e3f2fd,stroke:#1565c0
    style D fill:#fce4ec,stroke:#c62828
    style E fill:#f3e5f5,stroke:#6a1b9a
    style F fill:#e0f7fa,stroke:#00695c

各节核心知识点汇总

小节核心概念关键公式/定理与前后节的关联
13.1 语言与文法字母表、字符串、Kleene 闭包、文法四元组、派生、派生树、乔姆斯基分类 = {w ∈ T* : S ⇒* w}；0型 ⊃ 1型 ⊃ 2型 ⊃ 3型全章基础，定义语言和文法的形式体系
13.2 带输出的 FSMMealy 机、Moore 机、状态转移表/图Mealy: g: S×I→O；Moore: h: S→O13.1 文法的物理实现雏形；去掉输出→13.3
13.3 不带输出的 FSMDFA 五元组、NFA、语言识别、子集构造法M = (S,I,f,s₀,F)；NFA-DFA 等价13.2 去掉输出的特例；为 13.4 正则语言提供识别器
13.4 语言识别正则表达式、Kleene 定理、泵引理、下推自动机Kleene 定理：正则 ⟺ DFA 可识别；泵引理13.3 DFA 的理论深化；超越正则→13.5
13.5 图灵机图灵机、Church-Turing 论题、停机问题、P/NPChurch-Turing 论题；停机问题不可判定全章终极模型，统一所有计算概念

学习脉络

形式语言与文法（13.1）— 掌握文法四元组和乔姆斯基分类，理解语言的形式化描述
  ↓
带输出的有限状态机（13.2）— 理解 Mealy/Moore 机的区别，学会画状态转移图
  ↓
不带输出的有限状态机（13.3）— DFA/NFA 的定义和等价性，学会设计 DFA
  ↓
语言识别与正则表达式（13.4）— 正则表达式的定义和运算，Kleene 定理，泵引理
  ↓
图灵机（13.5）— 图灵机的定义和执行，Church-Turing 论题，停机问题

学习建议：13.1 节的乔姆斯基文法分类是核心框架，需要记住 0-3 型文法的产生式限制和对应的识别器；13.2-13.3 节的有限状态机需要手动练习状态转移图的设计（如识别特定模式的 DFA）；13.4 节的正则表达式需要掌握递归定义和等价变换；13.5 节的图灵机需要理解其与 DFA 的本质区别（无限带+读写头），并理解 Church-Turing 论题的哲学意义。

跨节综合复习题

综合复习题 1（跨 13.1 / 13.3 / 13.4）

题目： (a) 构造一个 DFA，识别字母表 {0, 1} 上所有包含偶数个 0 的字符串。 (b) 写出 (a) 中语言的正则表达式。 (c) 构造一个文法 G，使得 L(G) = (a) 中的语言。G 属于乔姆斯基的哪一型？

综合复习题 2（跨 13.4 / 13.5）

题目： (a) 用泵引理证明 不是正则语言。 (b) 构造一个图灵机来识别 L。 (c) 这是否与 Church-Turing 论题矛盾？为什么？

与其他章节的关联

关联章节关联方式
第1章 命题逻辑有限状态机的状态转移可以用逻辑命题描述；布尔电路是有限状态机的物理实现
第2章 集合形式语言是字符串集合；Kleene 闭包是集合运算
第3章 算法图灵机是算法的数学模型；Church-Turing 论题定义了”算法”的边界
第5章 递归文法的产生式是递归定义；递归下降解析器直接实现文法
第6章 计数字符串计数与 Kleene 闭包有关；泵引理利用鸽巢原理
第9章 关系状态转移函数本质上是关系；NFA 的转移关系是二元关系
第12章 布尔代数有限状态机的电路实现；状态编码使用布尔代数

📚 全书完结

离散数学知识库编译完成

至此，Rosen《离散数学及其应用》第8版全部 13 章的学习笔记和章节汇总已编译完成。

  • 笔记总数：84 篇（79 篇节笔记 + 5 篇章节汇总）
  • 概念页总数：122 个
  • 知识库总页数：214+

从第1章的逻辑与证明基础，到第13章的图灵机与可计算性，离散数学的完整知识体系已在 Obsidian 知识库中构建完成。每篇笔记都包含核心概念讲解、补充理解、习题精选和学术来源引用，并通过双向链接和概念页构建了跨章节的知识关联网络。

下一步：执行第13章的 Wiki Ingest（概念页编译），完成知识库的最后一块拼图。

关系图谱