CSCI3130 L10 图灵机变体 · Part 4 有界带与构造练习

课程：CSCI3130 Formal Languages and Automata Theory 本讲：L10 第 4 部分 / 共 4 部分（Outline 三部分及结尾段）· 原件 L10-图灵机变体-资料包.pdf（本地课件） p.125–131 定位：区分等能力的硬件变体与真正限制工作空间的模型，再完成复制串识别练习。 前后：上一份 非确定性、通用机与可数性 承接：#L10-05 多带模拟、#L10-07 非确定计算树、#L10-12 线性有界自动机

p.125 是 Linear Bounded Automata 分节页。

输入的两端成为工作空间边界（p.126–128）【已会】

p.126 The input string tape space is the only tape space allowed to use

图（p.127）：线性有界自动机的工作区。 元素：输入 abcde 放在左右端标记之间；工作区箭头指向这五个输入格，左右边界分别标为 Left-end marker、Right-end marker。 看什么：机器可以反复读写输入区，但不能向端标记以外扩展工作带。

标准图灵机能随着计算需要使用越来越多的空白格，这里取消了这种自由。允许的格数随输入长度增加，故不是有限自动机：后者的状态数不随输入增长。补充（通识）：常数倍线性空间可以压进有限多个轨道，用更大的有限带字母表表示；这解释了“只用输入格”和“使用线性空间”两种常见表述之间的关系。

p.128 给出三段等量语言和阶乘长度语言作为例子，并说明 LBA 比 NPDA 强、比一般 TM 弱。页上没有明确区分确定型与非确定型 LBA，因此这里不把二者的能力等价当作课件结论。

算一遍（用讲义语言，自取输入）：对 aabbcc，先检查段序为先 a 后 b 后 c；第一轮把最左未标记的 a、b、c 分别标成 A、B、C，得到 AaBbCc；第二轮得到 AABBCC。再次扫描没有未标记符号，接受。每轮必须找到三个匹配对象，否则拒绝。aabcc 第一轮得到 AaBCc，第二轮找不到新 b，拒绝。所有标记都在原六格或五格内完成。

p.128 两个原例的完整写法分别是 $L=\{a^nb^nc^n\}$ 与 $L=\{a^{n!}\}$。页上未另写 n 的起始范围；若纳入 n=0，应分别处理空串与0!=1的边界。第二个语言说明“允许线性空间”并不限于三段配对；本页没有提供阶乘识别机的转移图，不能把一个不存在的图遗漏误认为已给证明。

复制串题目与原图的边界问题（p.129–130）

p.129 是 Questions 结束页，p.130 另给构造题。

题面（L10-图灵机变体-资料包.pdf · 结尾构造题 · p.130，图片视觉读取；公式按原题重排）

p.130 Design a Turing machine that accepts the language $L=\{ww:w\in\{a,b\}^{+}\}$.

图（p.130）：两端标记的候选机器。 元素：初态 q0，唯一双圈终态 q5；q0 读 a/b 写 A/B 右移到 q1；q1 在 a/b 上原样右移，遇 A/B/空白原样左移到 q2；q2 读 a/b 写 A/B 左移到 q3；q3 在 a/b 上原样左移，遇 A/B 原样右移回 q0；q0 遇 A/B 原样右移到 q4；q4 遇 A/B 原样左移到 q5。 看什么：q2 不保存左端读到的是 a 还是 b，图中也没有比较两半对应字符的机制。

复核图中的所有边后，可以用 abba 检查：先标两端 a 得 AbbA，再标中间两个 b 得 ABBA。头返回第二格，q0 读 B 到 q4，q4 读第三格 B 到 q5，接受；但 abba 两半 ab 与 ba 不相等。反过来，对合法串 aa，标完得到 AA，q0 读第二格 A 进入 q4 后头在右空白，q4 无边可走，未接受。这两条轨迹说明该候选图不能直接作为原题的正确答案。

完整构造（补充，用多带变体解原题）：第一遍扫描输入，每读两格在第二带写一个计数符号；若输入为空或末尾剩单格，拒绝。此时长度为 2n，第二带恰有 n 个计数符号。把输入头移回左端，逐个消耗计数符号，同时将输入的前 n 个字符依次写到第三带。计数消耗完时，输入头恰在后半段首格；第三带头移回副本首格。之后逐格比较输入后半段和第三带副本；字符不同即拒绝，两者同时到末尾则接受，只有一者结束则拒绝。

每个阶段只扫描有限输入或有限计数，故一定停机。计数确保比较的是两个等长半段，逐格比较确保顺序和值相同；接受当且仅当输入为非空 w 的双份。多带机由 p.41–49 的模拟转换为标准单带 TM，不改变接受语言。

算一遍（自取输入演示）：abab 长4，第二带写2个记号；第三带复制前2格 ab，输入剩余 ab；比较 a=a、b=b，同时结束而接受。abba 第一次比较就是 a≠b，拒绝。这个检查也避开了把复制串误作回文的常见错误。

非确定图的分工与一条接受计算（p.131）

图（p.131）：以大写字母和 x 标记的非确定图灵机。 元素：初态 q0，唯一终态 qf。下表逐项转写原图；空白写作 □，S 表示原地不动，未列的转移不存在。 看什么：q4 读 a 时既可继续扫描，也可把它写成 x 并回头，这是非确定选择发生的位置。

页上只给机器图和标题，没有独立写出目标语言；结合上一页复制串题，可以观察它的匹配设计，但不能把这里不存在的题干补成逐字引文。若首字符 b，q0–q2 把整个串 a、b 互换再归位；全串统一互换保留“两半是否相同”。q3 开始标记前段；q4 猜测一个 a 作为对应点，q6 回到最近的大写标记，q7 再处理下一字符。q8–q9 承担 b 的匹配。最后 q10 向右检查是否只剩标记。

算一遍（自取输入演示原图）：abab 经 q3 标第一格得到 Abab；q4 越过第二格 b，在第三格 a 选择标 x，得到 Abxb。q6 左移至 A，再到 q7 标第二格 b 为 B，得到 ABxb。q8 越过 x 到 q9，将最后 b 标 x，得到 ABxx；回程进入 q7 时读到 x，q10 扫过剩余 x 到空白进入 qf。这是一条有限接受分支；不能要求图的每条选择分支都接受。

空间受限不表示运行步数同样线性（补充）

对长度 n 的输入，若机器只用 n 个工作格、有 q 个状态、带字母表大小 g，忽略端标记的固定小修正，配置总数至多 $q\,n\,g^n$：选一个状态、一个头位置、每格一种符号。存储格数随 n 线性增长，可能配置数却是指数级，所以机器可以在有限空间里运行极多步骤。确定机一旦重回同一完整配置就会循环；非确定机则要问这个有限配置图里是否存在接受路径，不能仅沿一条路径无限试。

复制串与回文都能用“先比较相应位置”的口语描述，但位置映射不同。长度4的 abab，两半同向对应是第1对第3、第2对第4；回文比较则是第1对第4、第2对第3。前者通过，后者失败。反例 abba 的结果恰相反。每次画转移前先写出要比较的下标关系，便能查出正文原图只标两端却没有验证同向对应的缺口。

本讲核心考点

• LBA 的限制是可用带空间随输入线性有界（p.126–128，C 级）。
• 复制串识别要比较两半同位置字符，不能只标记两端（p.130，C 级）。
• 构造算法须说明段边界、终止性与接受的充要条件（p.130，C 级）。
• 非确定选择接受只需存在有限成功分支（p.131，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：无

• 原件：L10-图灵机变体-资料包.pdf（本地课件），PDF p.125–131；图形标记已视觉核对。

• 本次独立学习修订：核对本讲131页文本，并视觉复核 p.20、38、45、53、81、114、128、130–131。