CSCI3130 T06 · Part 1 反转不等 PDA

课程：CSCI3130 · 2025T1 本讲：第1部分 / 共5部分 · T06-2025T1.pdf（本地课件） p.1–4 定位：把不相等分成符号不匹配、右长、左长三类并构造接受路径。 前后：上一单元 T05 · 下一份 Part 2 承接：#L07-01 NPDA、#L07-02 栈替换、#L07-03 终态接受

整讲导航：P1 p.1–4、P2 p.5–6、P3 p.7–8、P4 p.9–10、P5 p.11–12。

本辅导原件只给本题题面，下面的完整转移、推导或反证为学习补充；它们不是原页印出的参考答案。读栈配置时统一把栈顶写在最左，λ边不消耗输入。

标题与导航（p.1–3）

p.1标题日期2025年11月6日，p.2五题Outline，p.3高亮Problem 1。题目依次为反转不等、CFG转PDA、确定性、非CFL证明和计数不等式。

不相等有三种可核对的原因（p.4）【已会】

题面块（T06 · Problem 1 · PDF p.4；公式按讲义重排）：

p.4 Find an npda on $\Sigma=\{a,b,c\}$ that accepts the language $L=\{w_1cw_2:w_1,w_2\in\{a,b\}^{\star},w_1\ne w_2^R\}$

先把c左侧逐符号压栈，c之后栈顶顺序正好是左串的反转。两串不等当且仅当某位置符号不同，或右侧较长，或右侧较短。需要恰一个c；不含c和多于一个c都拒绝。

以下给完整转移族。栈顶写在最左，底符Z；初态P，匹配态R，不等已确认态D，读完后确认左侧仍长的终态F。终态集{D,F}。记“(状态,输入,栈顶)→(新状态,替换串)”，未列者无转移。

F无后继，只有输入已经全耗尽的分支才能在F接受，因此提前猜“右侧结束”不会误收。D只读a/b、不读c，确保第二个c无法接受。R在Z且输入空时不接受，这正是两侧相等。

算一遍：abcb a去空格即abcba，左侧压出baZ，右侧ba依次弹b、a，最后R/Z，拒绝。abcbb第一个b匹配，第二个b与a不同进入D，接受。abc右侧空而栈baZ，可λ到F接受；c两侧均空，不等不成立，拒绝。abcbaa在匹配ba后多一个a，R/Z读a进D，接受。

正确性：D只在已见证字符差异或右长时进入，F只在结束时栈有剩余时接受；反之每种不相等原因都对应一条上述接受路径。

非确定的猜测如何受完整输入约束（补充）

自取应该拒绝的 abcba，读到 c 后配置为 $(R,ba,baZ)$。此时可以沿 λ 边进入 F，但得到 $(F,ba,baZ)$，输入 ba 尚未消耗，而 F 没有后继，因此这条分支失败。另一条分支继续匹配 b、a，最终到 $(R,\lambda,Z)$，R 不是终态，所以也拒绝。这个例子说明“允许猜测结束”并不等于机器拥有读取输入结束的额外传感器；错误猜测由后续无法完成读取来淘汰。

在 D 中保留栈而不继续弹也有理由：一旦某个对应位置的字母不同，后面再出现什么 a/b 都无法修复已经发生的不相等；栈的计数任务已经结束。但语法外壳仍要检查，所以 D 没有 c 转移。若加上可读任意字母的循环，就会错误接受含两个分隔符的输入。这把“关系判定已完成”与“输入格式仍须合法”分开了。

本讲核心考点

• 不匹配与长度差必须全部覆盖，且输入恰有一个c（p.1–4，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：无

• 原件：T06-2025T1.pdf（本地课件），PDF p.1–4。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。原件12页只有题面与导航，解法明确标为补充。