Vince Jiang

CSCI3130 / 课程伴读 · 本站更新

CSCI3130 L00 Part 3/4 Course Contents

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1 本讲：L00 Part 3/4 Course Contents · 原件 L00-课程简介-2026T1.pdf（本地课件） p.16–30 定位：用输入、控制、输出和临时记忆理解自动机，并把有限自动机、栈机器和图灵机的能力差异连起来。 前后：上一份 L00-P2-学习目标.md · 下一份 L00-P4-计算理论导论.md

p.16 Outline 分节页。

Course Contents

先问能不能，再问有多难（p.17）【新】

p.17 Assuming that we can solve a problem, how hard is it to solve?

本页把课程分成自动机、形式语言与文法、可计算性、复杂性。前两项提供描述工具，后两项提出问题。**可计算性（computability）**问在指定模型下有没有算法；**复杂性（complexity）**问算法需要多少时间和空间。“我的实现很慢”不能推出“问题不可计算”；换一种算法也许会更快，而不可计算性的论证要排除所有算法。

把一台电脑拆成四种信息（p.18–19）【新】

图（p.18–19）：CPU 与记忆的分解。 元素：p.18 的 CPU 与 memory 双向连接；p.19 的 input memory 指向 CPU，CPU 指向 output memory，Program memory 指向 CPU，temporary memory 与 CPU 双向连接。 看什么：输入保存原始数据，程序规定操作，临时记忆保存中间结果，输出保存最后结果。四个用途不同，并非四种必然独立的物理硬件。

p.18 先给 CPU 与记忆两个大块；p.19 才按用途拆分。之后区分自动机，主要改变临时工作记忆的能力。不要把“输入串很长”误读成“机器拥有可随意使用的同样长工作空间”：读取输入与保存中间结果是不同许可。

用立方计算看中间结果（p.20–22）【新】

题面（L00-课程简介-2026T1.pdf · 立方算例 · p.20–22）

p.20 Example: f(x)=x3f(x)=x^{3}

p.21 x=2x=2

公式按讲义重排。p.20 的程序分两步：先算平方，再乘原输入。p.21 把输入设为 2。p.22 中临时变量 zz 保存 2⋅2=42\cdot2=4，然后 f(2)=z⋅2=4⋅2=8f(2)=z\cdot2=4\cdot2=8。之所以需要 zz，是第二次乘法需要第一次乘法的结果；只保留“当前执行到第几条指令”并不能凭空恢复任意大小的平方值。

输出与封装（p.23–24）

图（p.23–24）：算出结果后写入输出；将 CPU 和程序圈成 Automaton。 元素：p.23 output memory 写入 8；p.24 红框包含 CPU 与 Program memory，临时记忆、输入、输出位于红框外。 看什么：p.23 的 8 是最终输出，不只是临时存储。p.24 改变描述层级：把执行规则与执行单元一起视为控制部件，外部记忆结构单独讨论。

“自动机”在这里是数学抽象，并不要求造出一种新的实体硬件。我们关心每一步能读什么、写什么、记住什么。

有限状态与栈（p.25–27）【新】

p.25 Automata are distinguished by the temporary memory

p.25 以临时记忆区分模型；p.26 把 temporary memory 框划掉，表示有限自动机没有额外、可无限增长的工作空间。它仍有有限状态，状态本身可以保存少量信息。“没有临时记忆”不等于“历史对未来完全没有影响”。

图（p.26–27）：有限自动机与下推自动机。 元素：p.26 有限自动机的额外 temporary memory 被红叉划去；p.27 控制单元与 Stack 双向连接，栈顶标 Push、Pop，输入指向机器、机器指向输出。 看什么：栈（stack）允许积累任意多的标记，但只能从栈顶访问；压入叫 push，移走栈顶叫 pop。限制访问位置，正是这种模型能力受限的原因。

补充 · 算一遍（数字是我为演示取的，讲义没给）：从空栈依次压入 1、2、3，栈顶为 3；一次 pop 得到 3，剩下 1、2；再 pop 得到 2。若要访问最早的 1，必须先处理挡在它上面的元素。这个过程解释“后进先出”，不代表讲义给出了一台具体 PDA。

图灵机的能力与课程路线（p.28–30）【新】

p.30 General computation and its inherent limitations

图（p.28–29）：图灵机存储示意与能力顺序。 元素：p.28 以 Random Access Memory 框与 Turing Machine 双向连接；p.29 依次写 Finite Automata、Pushdown Automata、Turing Machine，并用小于号连接。 看什么：本导论用方便的存储直觉引入一般计算。补充：标准图灵机在后续讲义会用逐格读写的纸带严格定义；这里的 RAM 字样不能当成标准单带机“一步任意访问”的转移规则。

p.29 的“power”指可解决的问题范围，不是主频、功耗或运行速度。一台模型能模拟另一台，只能先推出能力包含，不能推出模拟没有时间成本。

p.30 按有限记忆、栈记忆、一般计算排列课程，随后研究算法的限制与复杂性。学习时可以围绕同一个问题反复问：换了记忆结构以后，以前无法保存的信息现在能保存了吗？

p.30 的完整课程路线按顺序是：Introduction to the Theory of Computation；Finite Automata；Regular Languages and Grammars；Context-Free Languages；Pushdown Automata；Turing Machines；Limits of Algorithmic Computation；Computational Complexity。标记 A 对应有限记忆，B 对应栈记忆，C 对应一般计算及其限制。页尾还把本课连接到 CSCI3120 Compiler Construction、CSCI3160 Design and Analysis of Algorithms、CSCI3360 Introduction to Computational Complexity。

补充：把三种记忆限制落实到一个动作。 假设输入持续送来左括号，再送来右括号。有限状态只能记住有限种历史摘要；栈可以每见一个左括号就压入一个标记，每见一个右括号就弹出一个标记。这说明栈为什么适合匹配嵌套。图灵机则可在工作带反复读写，不只访问栈顶。此处只是解释 p.25–30 的能力差别；具体语言及机器的严格定义仍按后续课件逐步建立。

考试角度：（C 级 通识）这类知识点常见考法是解释“有限状态也是记忆”，以及区分计算能力包含与运行时间比较。

两种“计数”需要的记忆并不一样（补充自取例）：只问读过多少个 a 是否为偶数，状态只需“偶/奇”，每读 a 切换，读 b 不变。a 的总数可以任意大，但答案所需的历史摘要只有两种。若要认出先 n 个 a 再 n 个 b，则读完 a 段后，后面必须核对任意大的确切 n；固定数目的状态会把某些不同 n 压到同一状态。栈可以每读一个 a 压一个标记、每读一个 b 弹一个，给两段建立一一配对。

以 aabb 为例，栈底为 Z、栈顶写在左边：Z → AZ → AAZ → AZ → Z。最后回到底部且输入读完，配对成功。aab 会留 AZ，abb 会在读完 ab 后就回到 Z，再读 b 时无 A 可弹；两者失败的理由不同。这只是栈记忆的演示；正式 PDA 还需要状态控制 a 段/b 段次序，不能仅比较总数。

本讲核心考点

  • 可计算性问是否存在算法，复杂性问资源代价（p.17；C 级）。
  • 临时存储与控制状态不是同一个概念（p.19、25–27；C 级）。
  • 模型能力比较不等于速度比较（p.29；C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.16–30。
  • 本次复核：2026-10-13；逐页读取上述原件文字，视觉核对结构图、课表、路线图及历史图页，补全具体内容。静态 PDF 外的视频未读取。