Notes on CS103 Mathematical Foundations of Computing
内容提要
文章介绍计算理论核心概念：集合势与康托对角线证明表明程序可数而问题不可数，故存在不可计算问题；命题逻辑与一阶逻辑基础；图论中的点覆盖、独立集、鸽巢原理与拉姆齐定理；有限自动机DFA/NFA、正则语言及其封闭性、正则表达式与Myhill-Nerode定理；上下文无关文法；最后提及图灵机。
延伸解读
可计算性的边界：从康托对角线到不可判定问题
文章用集合势与康托对角线证明串联起一个关键结论：程序作为有限字符串是可数的，而问题（字符串集合）的幂集不可数，因此必然存在大量不可计算、不可判定的问题。这一论证不依赖具体计算模型，而是从基数比较出发，说明“程序可数、问题不可数”是计算理论的根本限制。读者可借此理解为何存在物理计算机无法解决的问题，而非仅仅是技术暂时不足。
正则语言的封闭性：补运算与DFA状态翻转
文章指出正则语言在补运算下封闭，证明方式很直观：正则语言可由DFA识别，将DFA的所有接受状态与非接受状态翻转，就得到识别补集的DFA。这一构造说明封闭性不是抽象断言，而是有可操作的自动机变换作为依据。类似地，克林闭包、并、连接等封闭性也为正则表达式的自下而上构造提供了基础，使正则表达式与有限自动机之间的等价关系更易理解。
有限内存的局限：Myhill-Nerode与区分集
文章将DFA视为有限内存计算机，正则语言对应有限内存可解决的问题。Myhill-Nerode定理通过区分集给出判定非正则性的工具：若语言存在无限多个两两可区分的字符串，则它不是正则语言。文章以E={a^n b^n}为例说明其非正则性。这一视角把“非正则”与“有限内存无法解决”联系起来，帮助读者理解正则语言的能力边界，而非仅记忆定理表述。
从有限自动机到上下文无关文法：记忆的扩展
文章在介绍CFG时强调，推导过程通过递归建立了无限记忆的栈，这与DFA的有限内存形成对比。定理指出每个正则语言都是上下文无关的，说明CFG是更广的语言类。读者可注意CFG规则只有“→”而没有正则表达式中的“*”特殊操作，其表达能力来自递归结构。这一过渡为后续图灵机与可计算性理论埋下伏笔，呈现计算模型逐步增强的记忆能力。
Q&A
为什么说存在不可计算的问题？
因为程序是有限字符串，所以程序集合是可数的；而所有字符串集合的幂集是不可数的，问题集合至少与字符串集合的幂集等势，因此问题集合不可数。可数集无法与不可数集一一对应，所以必然存在大量不可计算、不可判定的问题。
实质蕴涵中前件为假时整个命题为真，这样规定有什么好处？
这种“空真”规定让推理规则简单且一致。例如证明“对所有n，如果n是偶数，那么n²是偶数”时，当n为奇数前件假，蕴涵自动为真，无需额外讨论；否则数学证明会变得非常繁琐。这是为了让数学体系顺畅运转而刻意设计的。
点覆盖和独立集之间有什么关系？
点覆盖是满足每条边至少有一个端点在该集合中的顶点集合；独立集是任意两点不相邻的顶点集合。一个顶点覆盖的补集必然是独立集，一个独立集的补集必然是顶点覆盖。
NFA和DFA有什么区别？它们识别的语言能力相同吗？
DFA的判定过程是确定性的，每个状态对每个输入字符只有唯一转移；NFA在每一步有有限个（可能为零个）选择，且允许不消耗输入的ε-转移。只要存在任意一个选择序列能进入接受状态，NFA就接受该输入。一个语言是正则语言当且仅当有NFA识别它，因此NFA与DFA识别能力相同。
如何证明一个语言不是正则语言？
可以使用Myhill-Nerode定理：如果语言L存在一个包含无限多个字符串的区分集S（即S中任意两个不同字符串都能被某个后缀区分开），那么L不是正则语言。例如E={aⁿbⁿ | n∈ℕ}是非正则的。
正则语言和上下文无关语言是什么关系？
每个正则语言都是上下文无关语言。上下文无关文法（CFG）通过递归规则定义语言，其推导过程具有无限记忆（通过递归建立栈），而正则语言对应有限内存可解决的问题。因此正则语言是上下文无关语言的真子集。
