CSCI3130 L00 Part 4/4 Course Preliminaries

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1 本讲：L00 Part 4/4 Course Preliminaries · 原件 L00-课程简介-2026T1.pdf（本地课件） p.31–65 定位：从售货机、最短路和旅行商三个例子区分状态、接受与输出、可解性与效率；最后看这些问题怎样形成计算理论。 前后：上一份 L00-P3-计算模型.md · 下一份 L01-P1-数学预备.md

p.31 Outline 分节页。

Course Preliminaries

语言与机器各回答什么（p.32–34）【新】

p.32 Abstraction of the general characteristics of programming language

p.32 将**形式语言（formal language）**作为研究对象：我们关注哪些符号串满足规则，暂时忽略日常语言的语气、情境和情感。符号组成串，规则描述哪些串属于语言。语言是一组串；某一个串是它的元素，不能把这两个层次混为一谈。

p.33 问售货机怎样工作，p.34 给出简化条件：只收 NT 5-dollar 和 10-dollar 硬币，所有饮品价格 20。关键不是记住每次投币的完整历史，而是保留足以决定下一步的信息：当前累计投入到哪一个档位。

题面（L00-课程简介-2026T1.pdf · 售货机构造 · p.34）

p.34 How to design a vending machine?

p.34 Only NT 5-dollar and 10-dollar coins are used.

p.34 Only drinks all of 20 dollars are sold.

下一页将这些条件落实成状态和带标签的箭头。

将历史压缩成五个状态（p.35–36）【新】

图（p.35）：售货机状态图。 元素：初态是金额 0，唯一双圈终态是金额 20；其余状态为 5、10、15。边为 0→5（投5）、0→10（投10）、5→10（投5）、5→15（投10）、10→15（投5）、10→20（投10）、15→20（投5或投10）。最后一条投10的分支退5；原图没有画出终态后的重置边。 看什么：箭头标签是本次投入，圆里的数字是已经积累的状态；输入 10 与状态 10 不是同一概念。

算一遍：投入 5、10、10，状态依次为 0→5→15→20；第三枚使总投入达到 25，饮料价格 20，所以退回 $25-20=5$。另一个历史 10、5 也到状态 15；从这一刻开始，两种历史对后续投币的处理完全相同，因此无需分别建状态。不能据此说机器完全“无记忆”：它把相关历史压缩在当前状态里。

p.36 把例子抽象为离散参数信息系统的动态行为。离散意味着我们按一步、一个符号、一种状态描述变化；并不是在计算每枚硬币下落的连续轨迹。模型的取舍由需要解释的行为决定。

将 p.35 原图换成可直接运行的表：

因此一次运行从 0 开始，逐枚硬币查表，第一次进入 20 即完成这次购买。最后一行保留“未规定”，因为原图没有重置或持续购买的边。补上自己想象的边，会变成另一台机器。

p.36 列的离散参数系统例子是 digital systems、nerve systems、languages、information transmission systems、human-environment interactions。共同点是能挑出离散事件与状态变化来建模，不是说这些真实系统所有细节都离散。

三种接口：生成、接受、变换（p.37–39）【新】

p.37 generator --- with output and without input

p.37 acceptor --- with input and without output

p.37 transducer --- both with input and with output

p.37 按接口区分三种角色。生成器产生串；接受器判断给定串是否合规则；转换器将输入变成输出。此处“acceptor 没有 output”指没有额外的输出字符串接口，并非它没有接受/拒绝的可观察结果。

p.38 用自然语言文法、接待机器人和 CFG 说明生成：文法的规则可以逐步产生一个句子。p.39 用数字锁、词法分析器和有限自动机说明接受：先收到输入，再检验是否属于允许的集合。一个语言可以同时由文法生成、由机器识别；后面会研究哪些生成模型和识别模型恰好等价。

p.37 的三个圆形接口图分别画“只有向外箭头”“只有向内箭头”“同时有向内和向外箭头”。这正对应上面的三类，不需要靠图中颜色判断能力强弱。p.38 的接待机器人照片标为 Pepper、2014；p.39 配数字锁照片。照片用于说明接口角色，不额外规定文法产生式或自动机状态。

变换和可解性分类（p.40–42）【新】

p.40 Compiler (translating high-level languages into machine codes)

p.40 中编译器不只是回答“源程序是否合法”，还要产生目标代码，因此作为整体属于转换器。实际编译器包含识别步骤，并不妨碍整个系统具有输入输出转换接口。

p.41 问计算模型解决问题的能力，并区分根本不能解决、资源不受限时可解决、有限资源下可处理的情形。p.42 用 undecidable、intractable、tractable 概括三类问题。补充：对有限输入，指数时间算法也可能最终终止；“实际资源不够”不能改说成“数学上没有算法”。这些导论词语需要在后续可判定性和复杂性章节中加上严格定义。

p.40 另外两个转换例子是 interpreter（在本页指自然语言翻译者）与 Turing machine（把符号串变换为另一符号串）；配图标注 Unitree robot, 2025。不要把这里的 interpreter 自动读成程序语言解释器，因为课件括号已经限定了 natural languages。

p.42 说明研究可计算性的实际用途：先认出已有的不可解性结果，避免继续寻找不可能存在的通用算法。它与 p.41 的资源分类连接起来：不存在算法、存在但资源代价太大、存在且资源可接受，需要不同应对方法。

统一计算模型的用途（p.43–45）【新】

p.43 To unify comparison, an abstract model is needed as the machine for executing problem solutions.

p.43 引入资源比较的共同尺度。若只比较两台实际电脑的秒数，硬件、实现和输入分布都会影响结果；抽象模型先规定什么算一步，再研究步数如何随输入规模增长。

p.44 说图灵机能够模拟人设计的算法步骤。补充：这里需要区分“对已形式化的某种机器给出模拟证明”和 Church–Turing thesis 对直觉上有效计算的主张；导论的概括不能直接当成已证明所有物理系统都等价于图灵机。

p.45 是 Trip Planning 引入图，把抽象的效率问题拉回路线规划。下一页是单源最短路，再下一页是遍访各城市的回路，任务不同，不能只因都画了图就套同一算法。

图（p.45）：Trip Planning 的地图与景点照片。 元素：地图圈出 San Francisco、Lake Tahoe、Yosemite National Park，叠放湖泊与山谷照片。 看什么：同一组地点可以提出两类不同问题——去某个目的地怎样最短，或把所有目的地走一遍怎样最短。照片是情境提示，不含需代入后页算法的距离数据。

最短路：固定起点到各点（p.46）【新】

p.46 Shortest path $P_v$ from $s$ to each other node $v\in V-\{s\}$

公式按讲义重排。$G=(V,E)$ 中 $V$ 是顶点集合，$E$ 是边集合；$s$ 是起点，$l_e$ 是边长且非负。路径长度应累加该路径经过的边；不能把图中没走的边也加进去。

图（p.46）：以 1 为源点的六顶点带权示例。 元素：边 1—2 为7、1—3为9、1—6为14、2—3为10、2—4为15、3—4为11、3—6为2、4—5为6、5—6为9；绿色路径从1经3、6到5。文字定义先说有向图，而配图连线不画箭头，此处只核图中路径的代价，不从无箭头擅自添加方向。 看什么：路径 1→3→6→5 长度为 $9+2+9=20$，比直接先走 1→6 再到5的 $14+9=23$ 小。

讲义列基本实现 $O(\lvert V\rvert^{2})$，Fibonacci heap 实现 $O(\lvert E\rvert+\lvert V\rvert\log\lvert V\rvert)$。这两个式子比较增长级别，不表示六个点恰好运行 36 秒。补充 · 算一遍：在图上从1出发，先确定3的距离9，经3可把6的14更新为 $9+2=11$，再经6把5更新为 $11+9=20$。这解释了最短路为什么要反复比较已有距离与新候选距离。

补充：按 p.46 给定边完整跑一遍距离更新。 距离代表从起点 1 已发现的最短候选路径长度。开始只有 1 的距离为 0，其余为无穷；确定一个当前最近且未确定的点后，用它的出边改善候选值。按图中无箭头连线的无向读法，过程如下；若采用文字所述有向图，则需另给每条边方向。

最终到 2、3、6、4、5 的最短距离分别为 7、9、11、20、20。这里使用非负边长，保证当前最近点不会在以后经一条绕路变得更近。原页把路径长度的求和下标写成整个 E；这里区分图的边集 E 与路径实际经过的边，只累加后者。

旅行商：必须绕完整一圈（p.47–48）【新】

题面（L00-课程简介-2026T1.pdf · Traveling Salesman Problem · p.47）

p.47 What is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

图（p.47）：六点旅行商示例。 元素：为便于叙述，给原图无名点临时命名 A（左上）、B（上中）、C（右中）、D（最下）、E（左下），S 为原图黄色起点。无向边 AB=5、BS=3、SC=2、CD=8、DE=3、EA=4、AC=1、EB=2、EC=6、SD=10；没有画出的边不允许走。 看什么：红色回路 S→B→A→E→D→C→S 的长度是 $3+5+4+3+8+2=25$。红色只是一个可行解，不是最优性的证明。

算一遍：S→C→A→B→E→D→S 得 $2+1+5+2+3+10=23$。要回答“least-cost”，还需排除别的回路更短；本图全部可行回路逐项核算见附录 A1，最小值确为 23。

p.48 给暴力枚举 $O(n!)$ 与动态规划 $O(n^{2}2^{n})$。后者比阶乘增长慢，但仍是指数级。补充 · 算一遍（数字是我为演示取的，讲义没给）：$10!=3628800$，$10^{2}2^{10}=102400$，只是代入增长表达式的量级对照，不能当成精确运行次数。讲义把寻找最短回路与 NP-Complete 放在一页；通行严格区分是：给阈值问是否存在不超过它的回路是判定版，求最短回路是优化版。不要把 NP 理解成“非多项式”的缩写。

p.48 的大地图展示美国 13,509 座人口至少 500 的城市，课件给出 tsp.gatech.edu 作为图片参考。它说明实例规模可以远超前页的六点图；不能把图上看起来密集的红线误认成已经枚举了全部路线。NP 的展开是 Non-Deterministic Polynomial，中文为非确定性多项式时间；“非确定性”修饰计算模型，并不是把 Polynomial 前面加一个否定词。

面对困难问题的三种结论（p.49–51）

p.49 I can’t find an efficient algorithm. I guess I’m just too dumb.

p.50 I can’t find an efficient algorithm, because no such algorithm is possible!

p.51 I can’t find an efficient algorithm, but neither can all these famous people.

p.49 的个人失败没有数学结论；p.50 是强得多的不可能性主张，必须证明；p.51 表示困难与一批公认困难的问题有关，也不能直接替换成“不存在高效算法”。这三页是学习归约的动机：把问题连接起来，可以转移已知难度，而不是靠尝试失败次数判断。

应用联系与形式化理想（p.52–54）

表（p.52）：领域与相关理论。

p.52 的表说明相同数学结构会被不同应用复用，不表示只掌握自动机就掌握整个 AI。p.53 提到 Hilbert 的问题清单，p.54 引出用公理与推理规则判定数学命题的理想。本课借这个历史动机问“机械执行的推理能走多远”；此处依讲义说明历史脉络，不把这几页的年份和概括当作独立历史考证。

p.53 的历史记录是 David Hilbert 在 1900 年巴黎 International Congress of Mathematicians 提出 23 个未解问题。p.54 原文写 “At beginning of 19th century”，并把理想表述为 Axiomatization of mathematics：通过 inference rules 和 axiom systems 决定数学命题真假。这里保留课件的世纪措辞作为原件记录，不把它与上一页 1900 年自动合并成准确历史时间线。

补充：理解这一步所需的两个词。 公理是形式系统允许直接使用的起点；推理规则规定怎样从已得命题走到新命题。公理化的理想不只是“能写出证明”，还希望有机械程序为每个待判命题得出决定。这就把哲学愿望转成之后可以研究的算法存在性问题。

不完备、自指与机器模型（p.55–57）

p.55 the truth of certain mathematical statements cannot be proved by the use of mathematical axioms.

p.55 用简短语句引入 Gödel 不完备性。补充：精确表述需要对形式系统的可有效公理化、足够表达算术、相应一致性条件作限定；“某系统不能证明某真命题”和“任何问题都不可计算”显然不同。这里记住形式化方法有边界即可，不从这句概要自行推出更强结论。

p.56 是 Barber Paradox 视频引入页，PDF 没有印出完整题面，因此不把自己记得的某一版理发师故事当作本页逐字题目。p.57 接着解释研究者转向：明确算法能力范围，设计理论机器，研究它们的限制。抽象机器先于某种实际制造技术出现也成立，因为数学模型首先是一套规则。

p.55 将 1931 年 Gödel 的不完备性接到“some mathematical problems cannot be solved by algorithms”，并称公理化的理想由此破裂；这是课件的历史叙述。补充：逻辑边界：一个系统中不可证明与一个问题不可判定不是同一个定义，二者之间需要额外论证，不能把 “That is” 当成任意情形都成立的等号。页中人物图片标注 Institute for Advanced Study。

p.56 的 PDF 是标题、黑色视频框和 YouTube 来源链接，静态页没有显示视频题干。因此本笔记可完整记录该静态页，但不声称看过链接中的视频。补充：自指为何会成为后续主题：把判定程序用于它自己，就可能构造“若它预测接受，我就拒绝”的反向行为；是否能合法编码这种自用，后面图灵机和停机问题会逐步说明。此处不把这个解释冒充视频内容。

从图灵模型到存储程序（p.58–60）

p.58 In 1936, Turing proposed the model of universal algorithm machine

p.58 将 Turing 与 Church、Kleene、Post 的不同形式化放在同一历史背景；本页的重点是“算法”开始能用精确对象讨论。p.59 讲 McCulloch、Pitts 的有限状态系统与神经网络建模，说明简单离散状态也能表达有意义的动态行为。p.60 讲 stored program：程序本身也是存储的信息。这为以后把机器描述作为另一台机器的输入提供直觉；此处没有给出编码方法，编码与模拟留待后续讲义。

以下按 p.58–60 保留课件的具体历史内容，作为讲义叙述而非独立历史考证：1936 年 Turing 提出 universal algorithm machine；Stephen C. Kleene、Alonzo Church、Emil Post 也提出其他形式的模型。1943 年 Warren S. McCulloch 与 Walter Pitts 以有限状态系统模拟生物神经网络；课件称他们是自动机理论先驱。1940 年代末 Von Neumann 提出存储程序思路；1951 年 Eckert-Mauchly Computer Company 建成 UNIVAC I，课件称其为世界首台商业可用计算机。人物照片旁分别标 Cambridge、Chicago、MIT、Princeton，属于图片说明，不是定义成立的条件。

补充：存储程序的关键差别。 若程序只能固定在机器接线里，改变算法可能要换机器；若程序是存储的信息，同一台执行装置可以读取不同指令。在数学模型中进一步把程序编码成串，就能问“给你一个程序和输入，另一程序能否预测它的行为”。这条问题链连接到后续 universal machine。

文法、正则表达式与语言描述（p.61–63）

p.62 He also proposed regular expressions to describe strings of symbols, and proved them equivalent to finite automata.

p.61 介绍 Chomsky 的文法模型及 CFG；它用有限规则描述可能无限多的句子。p.62 连接正则表达式与有限自动机：一种偏描述，一种偏运行，表达能力却可以相同。“写法不同”不等于“能表达的语言不同”。p.63 介绍 Backus–Naur form（BNF）在程序语言文法中的作用；BNF 是描述规则的记法，不是识别程序的全部算法。

p.61 的课件叙述是 Chomsky 在 1950 年代后期提出自然语言文法的数学模型，并把 CFG 的提出标为 1956 年。p.62 也标 1956 年：Kleene 用有限自动机模拟 McCulloch–Pitts 神经网络，提出正则表达式，并证明它与有限自动机等价。p.63 标 1959、1960 年，Backus 与 Naur 先后提出后来称为 BNF 的文法表示，用于描述 ALGOL-60，推动编译理论发展。照片文字标 Chomsky 为 Retired @ MIT、Kleene 为 University of Wisconsin–Madison；Backus 为 IBM，Naur 关联 Technical University of Denmark 与 Copenhagen University，并标两者 Turing Award。年份与图片机构说明都保留为该版课件信息。

补充：生成规则为什么能描述无限多串。 规则数量有限，并不表示只能用一次；只要允许反复展开，同一条规则就可以生成不同长度的结构。有限的是描述，不一定是语言中的成员数。这是以后看到递归产生式时必须分清的层次。

困难性的历史引入（p.64–65）

p.64 Intractable problems are also called NP-hard problems.

p.64 用 NP-hard 概括难解性，p.65 为 Questions 结束页。补充：导论这里采用宽泛措辞；严格的 NP-hard 是归约关系定义，不能只凭“运行很慢”认定。尤其 NP-hard 不自动意味着已证明不存在多项式算法；也不只覆盖判定问题。复习应把导论提供的动机与 L14 中的精确定义分开。

p.64 还把 Stephen A. Cook 的这一历史节点标为 1969 年，并写只有很小的实例才能由计算机解决；照片注明 University of California, Berkeley 与 Turing Award。这里保留讲义具体说法，学习时不能把“小实例可以求出”推成“大实例绝对不可求出”，也不能凭一个年份或人物名称替代 NP-hard 的归约定义。p.65 只有 Questions?，没有遗漏的题目条件。

为什么“最短路都求出来”还没有解决旅行商（补充）：最短路只关心端点与总代价，可以按题意经过一些中间点；旅行商还要记住已访问的城市集合，并禁止漏点或提前重复。正文从 S 出发的一条便宜路径即使代价更小，若没有覆盖六个城市，就不是候选旅行商解。检查候选答案应按顺序做：相邻城市是否有边 → 每个城市是否恰访问一次 → 是否回到起点 → 总价是多少。前三项是可行性，最后一项才可用于比较最优性。

优化与判定可以用同一例子区分：已知最优值 23，问“是否存在成本至多 22 的回路”答案为否；阈值 23 时为是。判定回答一位真假，优化要找最低可行阈值或给出最优路线；二者有关联，却不能在定义复杂度类别时省掉任务差别。

本讲核心考点

• 初态、终态、输入标签和状态含义要分开（p.34–35；C 级）。
• generator、acceptor、transducer 按输入输出接口区分（p.37–40；C 级）。
• 不可判定与效率困难不同（p.41–44；C 级）。
• 最短路与旅行商约束不同；旅行商图最优值23（p.46–48；C 级）。
• 归约式困难证据不是个人失败，也不等于无条件下界（p.49–51、64；C 级）。

附录

A1 旅行商图的全部回路（p.47）

沿用正文的 A、B、C、D、E 临时命名。回路固定从 S 出发；同一无向回路反向行走代价相同，因此每对正反路线只列一次。逐一选择下一点时，仅保留原图有边、尚未访问且最终能回到 S 的选择。

为什么枚举完整：S 只邻接 B、C、D，A 只邻接 B、C、E，D 只邻接 C、E、S。固定起点以后枚举其余五点的排列，逐对检验这十条边，去掉与反向重复的路线，恰好剩表中五条。最小成本是23。这里没有把图补成完全图，也没有把两点之间的间接最短路当作一条新边；若题目另规定允许经中间城市，则题意已经改变。

回到正文：旅行商（p.47–48）

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：L00-课程简介-2026T1.pdf（本地课件），PDF p.31–65。
• 本次复核：2026-10-13；逐页读取上述原件文字，视觉核对结构图、课表、路线图及历史图页，补全具体内容。静态 PDF 外的视频未读取。