CSCI3130 Lec 1–6 简略复习

本篇按讲次保留定义、算法和证明的主线。完整解释见详细复习。空串统一写作 $\lambda$ 。

Lec 1：数学对象与语言

集合与关系。 $A\subseteq B$ 表示每个 $A$ 的元素都在 $B$ 中；相等需互相包含。并是至少属于一方，交是同时属于两方，差 $A-B$ 是在 $A$ 不在 $B$ ，补集是指定全集 $U-A$ 。德摩根律为 $\overline{A\cup B}=\overline A\cap\overline B$ 、 $\overline{A\cap B}=\overline A\cup\overline B$ 。

划分要求各块非空、两两不交、合起来覆盖全集。幂集 $2^S$ 收集所有子集， $|S|=n$ 时有 $2^n$ 个成员。笛卡尔积 $A\times B$ 的成员是有序对，有限时大小为 $|A||B|$ 。

函数为每个已定义输入给出唯一输出；全函数对整个输入域都有定义，部分函数允许某些输入无定义。关系是有序对集合，不要求输出唯一。等价关系满足自反、对称、传递；等价类形成划分。这一结构用于 DFA 状态合并。

图与树。 有向边有方向，标记边还带符号。本课 walk 可重复边和点；path 不重复边；simple path 不重复顶点；cycle 回到起点；simple cycle 只重复起终点；loop 是自环。Euler tour 恰走每条边一次并回到起点，Hamiltonian cycle 恰经过全部顶点的简单环。

枚举简单路径用回溯，禁止进入当前路径已有顶点，返回时撤销标记；不能用永久全局标记代替。树连通无环，指定根后有父子关系；深度按边数计，根深度为 0，高度为最大深度。高度 $h$ 的二叉树最多 $2^h$ 个叶子，由两棵高度至多 $h-1$ 的子树相加归纳得到。

渐近界与证明。 $O(g)$ 是最终不超过固定常数倍 $g$ ， $\Omega(g)$ 是最终不少于固定正常数倍 $g$ ， $\Theta(g)$ 两者兼有。直接证明从前提推出结论，构造证明给出对象并验证；归纳先证明边界，再由较小情形推出当前情形；反证假定结论为假并推出矛盾。递归定义对象，归纳证明性质。平面直线划分的最大区域数满足 $R(0)=1,R(n)=R(n-1)+n$ ，故为 $1+n(n+1)/2$ ；达到上界要求无平行、无三线共点。

字符串。 字母表 $\Sigma$ 有限，字符串是有序的有限符号序列。 $|w|$ 是长度， $\lambda$ 长度为 0； $uv$ 是连接， $|uv|=|u|+|v|$ ，连接一般不交换。 $w^0=\lambda$ ， $(uv)^R=v^Ru^R$ 。前缀在开头，后缀在末尾，子串为任意连续部分。 $\Sigma^*$ 含所有有限串与空串， $\Sigma^+$ 只含非空串。

语言。 $L\subseteq\Sigma^*$ ， $\varnothing\ne\{\lambda\}$ 。语言连接 $L_1L_2=\{uv:u\in L_1,v\in L_2\}$ ，两份成员独立选择；反转 $L^R=\{w^R:w\in L\}$ 。

L^0=\{\lambda\},\quad L^*=\bigcup_{k\ge0}L^k, \quad L^+=\bigcup_{k\ge1}L^k.

$L^*$ 总含空串； $L^+$ 是否含空串取决于 $L$ 是否含空串。因此 $L^+=L^*-\{\lambda\}$ 只在 $\lambda\notin L$ 时成立。 $L\{\lambda\}=L$ ， $L\varnothing=\varnothing$ ， $\varnothing^*=\{\lambda\}$ 。

文法。 $G=(V,T,S,P)$ 分别是变量、终结符、开始变量、产生式， $V\cap T=\varnothing$ 。 $\Rightarrow$ 为一步替换， $\Rightarrow^*$ 为零步或多步。句型可含变量，生成语言只收纯终结符串： $L(G)=\{w\in T^*:S\Rightarrow^*w\}$ 。证明文法恰好生成目标语言，要证明不生成非法串，也不漏合法串；两个文法等价只要求语言相同。

Lec 2：自动机

DFA 为 $M=(Q,\Sigma,\delta,q_0,F)$ ， $\delta:Q\times\Sigma\to Q$ 是全函数。每状态、每字符恰有一个后继，缺失转移需补到拒绝陷阱。扩展函数满足

\delta^*(q,\lambda)=q,\qquad \delta^*(q,wa)=\delta(\delta^*(q,w),a).

必须读完整个输入才检查是否在 $F$ ；空串被接受当且仅当初态在 $F$ 。状态表示已读前缀中未来仍需的信息：余数、阈值计数、模式匹配进度或它们的组合。读入 $b$ 进制数字 $a$ 时，数值余数更新为 $(br+a)\bmod d$ 。固定模式匹配保存“已读串后缀与模式前缀相符的最长长度”；包含、禁止包含、以模式结尾三种条件的接受后行为不同。

NFA 的转移为 $\delta:Q\times(\Sigma\cup\{\lambda\})\to2^Q$ ，允许多后继、空集合和不消耗字符的空串边。接受要求存在一条完整接受运行，不是随机选择一条路。

令 $E(S)$ 为只走空串边的可达闭包，包含 $S$ 本身。模拟从 $E(\{q_0\})$ 开始，每读一个字符 $a$ ，更新为

E\left(\bigcup_{q\in S}\delta(q,a)\right).

最终集合与 $F$ 相交就接受。初始与每次读字符后都要做闭包。用图搜索和访问标记计算闭包，空串环不会导致无限处理。

子集构造把上述每个集合变成一个 DFA 状态，用队列从初始闭包扩展全部字符转移，只建立可达子集；接受集合必须与原 $F$ 相交。空集为拒绝陷阱， $k$ 状态 NFA 最多产生 $2^k$ 个 DFA 状态。读每个前缀后，DFA 的集合恰等于 NFA 的全部可能状态，故两者语言相同。DFA 是 NFA 的特例，因此二者恰接受正则语言。

NFA 变成单一接受态：增新状态 $f$ ，每个旧接受态加空串边到 $f$ ，取消旧接受标记，只保留 $f$ 接受且无出边。原来无接受态时， $f$ 不可达，仍接受空语言。

DFA 最小化先删除不可达状态，再按接受/非接受初分组。若同组状态对某字符的后继落在不同组，继续拆分，直到稳定；最后每组合成一状态。不同组有区分后缀，同组对所有后缀接受结果相同，所以合并正确且不能继续减少状态。

Lec 3：正则表达式与文法转换

正则表达式的基本项是 $\varnothing,\lambda,a$ ；操作是并 $+$ 、连接、星号 $*$ ，优先级为星号、连接、并。 $L(r)$ 才是表达式描述的语言：

L(r+s)=L(r)\cup L(s),\quad L(rs)=L(r)L(s), \quad L(r^*)=L(r)^*.

表达式等价指语言相同。 $r+\varnothing=r$ ， $r\lambda=r$ ， $r\varnothing=\varnothing$ ， $\varnothing^*=\lambda$ 。构造表达式需要完整描述可选分支、连接顺序和重复片段，包括合法空串与短串。

RE 转 NFA按结构递归：基本项为无通路、空串边或字符边；并用空串分叉与汇合；连接把前一出口接到后一入口；星号增加零次直达边和重复返回边。片段分别实现对应语言运算，结构归纳证明整体正确。

NFA 转 RE先加独立新初态和新终态，构造边标记为 RE 的广义转移图；无边记 $\varnothing$ ，平行边取并。消去中间状态 $k$ 时，使用这一轮旧标签更新全部保留状态对：

R'_{ij}=R_{ij}+R_{ik}(R_{kk})^*R_{kj}.

第一项是不经 $k$ ，第二项是进入 $k$ 、绕任意圈再离开。消去全部原状态后，新初态到新终态的标签就是结果。各轮保留全部原路径语言，故转换正确。两方向构成 Kleene 定理。

正则文法必须统一右线性 $A\to uB\mid u$ 或统一左线性 $A\to Bu\mid u$ ， $u$ 为终结符串。线性只要求右侧至多一个变量，范围更大；混合左右方向不能直接算正则文法。

右线性转 NFA：变量作状态， $A\to uB$ 变为读 $u$ 到 $B$ 的路径， $A\to u$ 变为读 $u$ 到新接受态的路径；多字符用中间节点，空串用空串边。NFA 转右线性： $q\xrightarrow a p$ 变 $q\to ap$ ，空串边变单位规则，每接受态加 $q\to\lambda$ 。

左线性先把右侧反转成右线性，得到原语言的反转；再转 NFA 并反转机器，得到原语言。DFA、NFA、RE、正则文法四种表示具有相同表达能力。

Lec 4：封闭性与非正则性

运算	保持正则性的构造
并、连接、星号	组合 NFA 的入口、出口与空串边
反转	反向全部边，新初态用空串边连到所有旧接受态，旧初态成为唯一接受态
补集	完整 DFA 交换接受与拒绝状态
交、并、差	乘积状态 $(p,q)$ 同步更新，以相应布尔条件接受
同态	每字符 $a$ 固定替换为 $h(a)\in\Gamma^*$ ，在表达式或字符边上替换

同态满足 $h(uv)=h(u)h(v)$ ，可把某些字符替换为空串。NFA 不能直接交换接受标记求补。

判定算法。 成员判定用 DFA 逐字符模拟；空语言判定查初态能否到接受态；无限性判定在“初态可达且可到接受态”的 DFA 子图中查环；等价性判定构造对称差并检查是否为空。无限性中的环必须在成功路径上并能消耗正长度，纯空串环不够。有限表示转成 DFA 的成本应与后续搜索成本分开。

泵引理。 若 $L$ 正则，则存在 $p\ge1$ ，对每个 $w\in L,|w|\ge p$ ，存在 $w=xyz$ ，满足

|xy|\le p,\quad |y|>0,\quad \forall t\ge0:\ xy^tz\in L.

来源是 $p$ 状态 DFA 读前 $p$ 个字符时经过 $p+1$ 次状态位置，必重复一个状态，重复段形成可绕任意次的环。有限语言也满足引理，取足够大的 $p$ 即可。

证明非正则的顺序：假设正则并取得未知 $p$ ；自行选合法长串 $w$ ；覆盖所有合法分解 $xyz$ ；对每个分解找到某个使泵后串出界的 $t$ 。不能自行指定唯一分解。若 $|y|=d$ ，泵后长度改变量为 $(t-1)d$ ；可利用分段数量关系、排列、镜像或合法长度间隔推导明确矛盾。泵引理是必要条件，不能用它证明正则。

另外两种路线：假设正则后，通过与正则语言求交、取补或同态得到已知非正则语言；或找无限多个两两可区分的前缀，每对有相同后缀使接受结果不同，迫使自动机有无限状态。

Lec 5：上下文无关文法与解析

CFG 每条规则为 $A\to\alpha$ ，左侧单一变量，右侧任意变量和终结符串。它允许不依赖邻居地展开变量。CFL 是可由 CFG 生成的语言，包含全部正则语言。

递归两端加符号可表达嵌套与匹配，连接两个变量可表达并列。合法括号串要求总数平衡且每个前缀的左括号数不少于右括号数；总数相等不能代替前缀条件。合法串可分解为第一对匹配括号内的合法部分与后续合法部分，构成递归文法的完整性依据。

语法树根为 $S$ ，内部节点按产生式展开有序孩子，完整树叶子为终结符或空串；从左到右的叶子序列是 yield。部分树允许叶子仍含变量。最左与最右推导固定展开顺序，同一树对应唯一最左推导和唯一最右推导，但二者步骤先后不同。

歧义要求同一串有两棵不同语法树，等价于两份不同最左推导或两份不同最右推导；两份任意推导不够。表达式以 $E$ 加法层、 $T$ 乘法层、 $F$ 原子/括号层表达优先级，递归方向表达结合性。dangling else 需要确定它绑定哪层 if。文法有歧义与语言固有歧义不同，后者要求所有等价 CFG 都有歧义。

解析从给定串寻找推导或树。穷举最左推导可能指数增长，一般文法在拒绝输入上还可能不停；去除空串和单位规则后，长度 $n\ge1$ 的成功推导最多 $2n-1$ 步，因为增加句型长度的步数最多 $n-1$ ，变量变终结符的步数最多 $n$ ，故可以有限深度拒绝。

s-grammar 规则 $A\to a\alpha$ ， $\alpha$ 只含变量，且每对 $(A,a)$ 至多一条规则。栈顶变量与下一个输入字符决定唯一规则；消费该字符，把后部变量逆序压栈。输入和栈同时耗尽才接受，固定文法下时间 $O(n)$ 。GNF 不保证这个唯一性。

编译中，词法分析产生 token，语法分析产生树，语义分析检查类型等条件，代码生成形成指令。BNF 是产生式记法；LL、LR 是支持专门高效解析的文法类别，不等于全部 CFG。

Lec 6：文法变换与 CYK

替换原则。 对不同变量 $A\ne B$ ，把 $A\to uBv$ 展开为 $A\to u\beta_1v\mid\cdots\mid u\beta_kv$ 时，必须包含 $B$ 的全部规则候选，才能删除旧规则。它把两步合为一步而保持生成语言。

删除空串规则。 反复计算 nullable 集合：直接产生空串者先加入，右侧全由已可空变量组成者再加入。对每条规则的每个可空出现位置独立枚举保留/删除，加入非空结果，再删内部空串规则。若原语言含空串，使用不出现在右侧的新开始变量并保留其空串规则。可能有指数多个删位组合。

删除单位规则。 计算每个变量沿单位边的可达闭包，包含自身；把闭包内各变量的非单位规则复制到起点变量，再删除单位规则。访问标记处理单位环，不能无穷代入。

删除无用部分。 先由纯终结符规则开始求 generating 固定点，删掉不能完成终结符推导的变量和规则；再在删减后的文法中从 $S$ 求 reachable，删除不可达部分。整体顺序为空串、单位、无用，因为前面的变换会引出后面的待清理规则。

CNF 只允许 $A\to BC$ 或 $A\to a$ ，可另保留独立开始符号的空串例外。清理后，在长度至少 2 的右侧用 $T_a\to a$ 替代终结符，再把长变量串拆成二元链。原单字符规则直接保留。非空长度 $n$ 的 CNF 树有 $n$ 次终结符规则与 $n-1$ 次二元规则。

GNF 只允许 $A\to aA_1\cdots A_k$ 、 $k\ge0$ ，可有相同空串例外。每次最左推导产生一个新终结符，成功生成长度 $n$ 的串恰用 $n$ 步。转换用首变量代入、消除左递归、把首字符后终结符换成变量；一般算法先从 CNF 出发，按变量编号消去较小编号的首变量和直接左递归，再逆序代入较大编号，最后整理新增变量。详细稿给出完整步骤和左递归变换公式。

CYK 以 CNF 为前提， $V[i,j]$ 保存能生成连续子串 $w[i..j]$ 的全部变量。边界是 $V[i,i]=\{A:A\to w_i\}$ ，转移为

V[i,j]=\bigcup_{k=i}^{j-1} \{A:A\to BC,\ B\in V[i,k],\ C\in V[k+1,j]\}.

A → BC
    │
    ├── B 生成 w[i..k]
    └── C 生成 w[k+1..j]

从短子串到长子串，枚举全部切分点与二元规则

最终 $S\in V[1,n]$ 当且仅当串属于语言。正确性按长度归纳：加入的变量能通过两棵子树生成该串；任意成功树根必有一个二元规则和切分点，因此算法不会遗漏。空输入单独检查开始符号是否可空。

时间 $O(n^3|P|)$ 、空间 $O(n^2|V|)$ ；固定文法下简写为 $O(n^3)$ 、 $O(n^2)$ 。给每个加入的变量记录一条规则和切分点，就能从顶格恢复一棵语法树。

考试证据：本次未使用试卷作为讲解依据；内容按 Lec 1–6 原始课件重新编写。