CSCI3130 T07 · Part 2 双带偶回文

课程：CSCI3130 · 2025T1 本讲：第2部分 / 共4部分 · T07-2025T1.pdf（本地课件） p.5–7 定位：逐边核查原双带图并修正比较方向，接受非空偶回文。前后：上一份 Part 1 · 下一份 Part 3 承接：#L10-05 多带图灵机、#L09-02 停机与不接受

形式定义与配对策略（p.5–6）【已会】

p.5为Problem 2导航。

题面块（T07 · Problem 2 · PDF p.6；公式按讲义重排）：

p.6 Give a formal definition of a two-tape Turing machine; then write programs (Transition Graph or Transition Function) that accept the languages $L=\{ww^R:w\in\{a,b\}^{+}\}$ . Assume that $\Sigma=\{a,b\}$ and that the input is initially all on tape 1.

双带机使用两个读写头，转移按 $(q,s_1,s_2)\mapsto(q',t_1,t_2,d_1,d_2)$ ，方向各为L/R/S；其余有限控制、字母表、初态和终态含义与单带同。带1初始为输入，带2空白，各头在约定起始格。S可由标准动作模拟，不增加能力。

原解每轮标记最左未处理字母为A/B，再将最右未处理字母擦掉并写到带2，带2头向左移。如此带1保存左半，带2最终从左到右保存原右半，随后沿图与相应恢复的左半比较。需要特别留意写入顺序与磁带空间顺序相反；不能只说“把右半倒着取出”就认定磁带上也是倒序。

形式上可写 $\delta:(Q\setminus\{q_{\rm acc},q_{\rm rej}\})\times\Gamma^2\to Q\times\Gamma^2\times\{L,R,S\}^2$ （允许部分定义时未定义即停机拒绝）。一个配置要同时给两条带的内容、两个头位置与同一个控制状态；只写一条带的头位置不够定义此模型。

原状态图的全部转移与实际检验（p.7）

图（p.7）：初态q0，唯一终态q7，状态q0至q7。边标签以两带各自“读;写,方向”并列。以下用□为空白，将原图全部边转成表；s∈{a,b}，大写S是s对应标记A/B，未列者无动作。

起止	带1动作	带2动作
q0→q1	s→S,R	□→□,S
q1→q1	s→s,R	□→□,S
q1→q2	□→□,L	□→□,S
q2→q3	s→□,L	□→s,L
q3→q4	s→s,L	□→□,S
q4→q4	s→s,L	□→□,S
q4→q0	S→S,R	□→□,S
q3→q5	S→s,L	□→□,S
q5→q5	S→s,L	□→□,S
q5→q6	□→□,R	□→□,R
q6→q6	s→s,R	s→s,R（两带同一s）
q6→q7	□→□,R	□→□,R

看什么：q6同向比较两带，而前段分割将右半按原顺序留在带2。因此这份原图实际检查的是两个相同半串，不是题目要求的反转半串。 输入abab：先标A并取尾b到带2，下一轮标B并取a写到其左，带1恢复为ab，带2为ab，于是接受；但abab不是非空偶回文。abba则恢复出ab/ba，在q6第一格不同而拒绝。原页p.6文字中“in a reverse order”不能消除具体头移动造成的这一问题。

补充（沿原图最小修正）：保留q0至q5的分割。q5已把带1头移到左边空白、带2头在右半副本左边空白。先让带1右移到左半首格；带2右移扫描至副本右侧空白，再左移一格。之后比较时带1向右、带2向左，同字符才继续；带1到右侧空白且带2到左侧空白时接受。这恰检查左半正向与右半反向相同。以下三种状态给出替换q5出口后的完整尾部，带1符号u在扫描带2时保持不动：

起止	条件与动作
q5→r	两头读□：带1保持□并R，带2保持□并R
r→r	带2读a/b：两带均原样写，带1S、带2R
r→c	带2读□：原样写，带1S、带2L
c→c	两带同为a或同为b：原样写，带1R、带2L
c→q7	两带同为□：原样写，均S

其余情况拒绝。输入aa按修正后比较a/a接受；abba比较a/a、b/b接受；abab首个比较a/b拒绝。奇数长度在某轮q2读到大写标记而无动作，拒绝；空串在q0无动作，拒绝，符合w非空。每轮消去两个未处理字符，初始化/扫描有限，最后比较有限，故总停机。

这是原图的完整核对及修正构造，不把印刷图当已验证正确答案。

给两条带各标一组坐标（补充）

设输入长2n，带1从位置0开始存放 $x_1\cdots x_{2n}$ ，带2初头也在0。第 k 轮取出的右端字符是 $x_{2n-k+1}$ ，写在带2位置 $1-k$ 。因此分割完成后，带2从左到右的非空区 $1-n,\ldots,0$ 依次是 $x_{n+1},\ldots,x_{2n}$ ，不是反序。这一坐标等式解释了原图问题，避免仅凭“取出的时间顺序”猜测磁带上的空间顺序。

修正尾部先把带2头移到0，再反向比较。第 j 次比较（j 从0计）前，带1头在 j、带2头在 −j；比较的正是 $x_{j+1}$ 与 $x_{2n-j}$ 。通过 n 次后，两头分别到 n 与 −n，两处都是空白，且此前每对都相同，故原串是非空偶回文。若有任何不同，比较态没有转移，直接拒绝。分割成功已保证两半等长，因此不需要在比较时重新猜中点。

自检：为什么输入 aba 不能把中心 a 同时当成左右两边？

最后一轮先标左端，再到右端取字符；中心格此时是什么符号？

展开推理与答案

中心 a 已被标成 A，q2 只对小写 a/b 有取尾转移，所以在 A 上卡住并拒绝。不能另外加一个跳过中心的动作，否则目标会扩展成允许奇数长度的回文。

本讲核心考点

双带图要核对空间次序与读头方向，奇数和空串需拒绝（p.5–7，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：无

原件：T07-2025T1.pdf（本地课件），PDF p.5–7。
本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页7、10的全部转移。