Vince Jiang

CSCI3130 / 课程伴读 · 本站更新

CSCI3130 L04 Part 2 判定问题

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L04 Part 2 判定问题 · 原件 L04-正则语言性质-资料包.pdf（本地课件） p.33–44 定位：把成员、空性、有限性和等价性化成有限图上的算法。 前后：上一份 L04-P1-封闭性质.md · 下一份 L04-P3-非正则语言.md

p.33 Outline，进入关于正则语言的算法问题。

输入必须有有限表示（p.34–36）

p.35 Language L is in a standard representation

p.34 列出 DFA、NFA、RE、RG；p.35 “给定一个正则语言”指拿到这样一份有限描述，而非先列出无限所有成员。p.36 的成员问题是给定具体串 w，判断它是否属于 L：转成 DFA 并逐字运行，输入读完看当前状态是否终态。算法必终止，因为每一步消耗一个输入字母。

成员测试与空语言测试不是同一个问题（p.37–39）

p.37 两幅图分别表达固定串被接受或拒绝，不能从某个串失败推断整个语言为空。p.38 判断空语言只需查初态能否到任意终态；边上任何有限标签路径都是一个见证串。p.39 上下图展示可达和不可达情况：搜索全部有限状态，不需要枚举全部无限字符串。若初态已是终态，长度零的路径已足够证明非空。

补充算例（演示串自取，沿用 L04 p.20–23 的交集乘积机）：从 AX 广度搜索，读0到 BY，再读1到 AZ，找到见证01。因此它非空。要测试某个具体输入001，则到 CZ，拒绝；两句话不矛盾。

无限语言要求有用的环（p.40–41）

p.40 Check if there is a walk with cycle from the initial state to a final state

环必须既从初态可达，又能到终态。DFA 每条边消耗一个符号，多绕一次环增加正长度并仍可结束，于是有无限多不同长度的串。孤立环、只能进入而永远到不了终态的死环，都不够。

补充算法说明：先保留初态可达的状态，再保留能到终态的状态，在交集中检查有向环。若无环，接受路径长度受有限状态数约束，只可能有有限个串。这里采用 DFA；若直接看含空边的 NFA，纯空边环不增加串长度，不能照搬“见环即无限”。

等价问题化成对称差为空（p.42–44）

题面（本讲 · p.42；公式按讲义重排）

p.42 Given regular languages L1L_1 and L2L_2 how can we check if L1=L2L_1=L_2?

构造

D=(L1∩L2‾)∪(L1‾∩L2). D=(L_1\cap\overline{L_2})\cup(\overline{L_1}\cap L_2).

p.43 若 D 为空，两边都没有“只属于自己”的串，互相包含，故相等。p.44 若 D 非空，其任意成员就是区分两语言的反例。乘积 DFA 中，把“恰有一分量为终态”的状态设为终态，再跑可达性搜索，就把证明转成有限步骤。

补充算例（条件取自 L04 p.17）：L1L_1 不含00，L2L_2 以01结束。空串属于前者而不属于后者，因此初始乘积态 AX 已满足异或接受条件，立刻证明两语言不等，无需搜索更长字符串。

考试角度：（C 级 通识）常见考法是区分不可达环、无出口环和位于接受路径上的环，以及用对称差给出最短不等价见证。

考试角度：（A 级：期末-2022T1-资料包.pdf Q6，对应正则表达式是否包含全部偶数长串；扫描件视觉读取。）见附录 A1。

一次搜索同时给结论和见证（补充）

等价测试不必先生成全部字符串。建立乘积初态后做广度优先搜索，记录每个新状态的“从哪个父状态、读哪个字符第一次到达”。遇到一终一非终的乘积态时，从该态沿父指针回溯，再把字符顺序反转，就得到最短区分串。之所以最短，是 DFA 每边恰消耗一位，广度搜索按路径边数递增；若直接在带空边的 NFA 图上按边数搜索，则边数不等于输入长度，不能照称最短串。

若搜索完都没遇到异或终态，也有可核的否定证据：初态所在的整个可达集合已经封闭于所有字符转移，而每一对状态的接受性一致。任何输入的轨迹都留在这个集合，所以不存在遗漏的区分串。有限个状态对保证队列最终清空，避免“再测试更长一点”永无终点。

自检：一台 DFA 有环，但所有终态均不可达，其语言无限吗？

先做空性检查，再问环是否位于接受路径上。

展开推理与答案

语言为空，因而有限。无论有多少环，都没有串能从初态到终态；“有用环”必须同时满足初态可达与可达终态两个方向，不能只检查前者。

四个算法各自在有限什么（p.36–44）

问题 具体输入 有限搜索对象 返回“是”的条件
成员 DFA 与一个串 w w 的每个位置 读完停终态
语言为空 DFA 初态可达状态 可达集合与终态集无交
语言有限 DFA 既可达又可到终态的子图 其中没有有向环
两语言相等 两台同字母表 DFA 可达状态对 每一对的终态资格一致

“空”与“不含空串”完全不同。只接受 a 的机器不含空串，但语言不空；只接受空串的机器语言也不空，而且有限。若有 n 个有用状态且有用子图无环，接受路径不可能重复状态，长度至多 n−1；有限字母表上长度有统一上界，才推出串的总数有限。

本讲核心考点

  • 固定串成员测试与全语言空性（p.36–39，C 级）。
  • 初态到终态路径上的环（p.40–41，C 级）。
  • 对称差为空与语言等价（p.42–44，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：正则表达式是否包含全部偶数长串

题面块（期末-2022T1-资料包.pdf（本地课件） · Q6 · p.4，扫描件视觉读取）：

p.4 Given an algorithm to decide the following language. Here R is a regular expression over {a,b}.

p.4 L={⟨R⟩:Every string of even length is accepted by R}L=\{\langle R\rangle:\text{Every string of even length is accepted by }R\}.

把R转为完整DFA D，再取补得到不被R接受的串；另建两态DFA E接受偶数长度（初态为偶且终态，每个字符切换奇偶）。作乘积接受E与D补的交。从乘积初态做有限图搜索；若可达某终态，说明存在一个偶数长反例，回答NO；否则回答YES。有限状态搜索总会结束，故是判定器。

正确性双向：任何可达接受状态有一条输入标签w，E接受说明w偶长，D补接受说明R遗漏w；反之任何遗漏的偶长串必给出这样一条路径。λ也属偶长，所以若D初态非接受，乘积初态就是反例，不可漏查。自取R=(aa+ab+ba+bb)星时没有反例；R=(a+b)正闭包则因漏λ而回答NO。

回到正文：正则表达式是否包含全部偶数长串

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

  • 原件：L04-正则语言性质-资料包.pdf（本地课件），PDF p.33–44。

  • 本次独立学习修订：核对本讲全部103页的文本，视觉复核 p.16–17、21、26、42、54–56、102–103；图示以表格、轨迹和证明展开。