CSCI3130 期中详细复习：语言、自动机与文法

范围为 Lec 1–6。本文从原始课件重新编写，按讲次分章，完整说明概念、构造算法和证明依据。公式中的空串统一写作 $\lambda$ ；写作 $\varepsilon$ 时含义相同。简略复习用于回顾本篇已经解释过的内容。

这六讲围绕同一个问题展开：给定一串符号，怎样准确描述它是否属于某种语言，并用算法作出判断？ 集合和证明提供表达工具；有限自动机用有限个状态读入字符串；正则表达式和正则文法描述同一类语言；上下文无关文法进一步表达递归结构；最后把文法整理成便于分析的形式，用 CYK 算法判断字符串是否能生成。

Lec 1：把语言写成准确的数学对象

集合、集合运算与划分

集合由元素构成，元素是否属于集合是明确的判断。 $x\in A$ 表示 $x$ 是 $A$ 的元素， $A\subseteq B$ 表示 $A$ 的每个元素都属于 $B$ 。两个集合相等，就是互相包含。因此证明 $A=B$ 时，可以分别证明 $A\subseteq B$ 和 $B\subseteq A$ 。

集合中的元素没有排列顺序，同一个元素重复列出也不会增加集合大小。空集 $\varnothing$ 没有任何元素。有限集合的基数 $|A|$ 是其中不同元素的个数；真子集 $A\subsetneq B$ 则在包含关系之外，还要求 $A\ne B$ 。

运算	元素属于结果的条件
并集 $A\cup B$	属于 $A$ 或属于 $B$ ，两者都属于也可以
交集 $A\cap B$	同时属于 $A$ 与 $B$
差集 $A-B$	属于 $A$ ，但不属于 $B$
补集 $\overline A=U-A$	在指定全集 $U$ 内，但不属于 $A$

补集必须相对于同一个全集理解。德摩根律把“不是至少满足一个”改写为“两个都不满足”，把“不是同时满足两个”改写为“至少一个不满足”：

\overline{A\cup B}=\overline A\cap\overline B, \qquad \overline{A\cap B}=\overline A\cup\overline B.

$A\cap B=\varnothing$ 称为不相交。一个集合的划分，是一组非空、两两不相交、合起来恰好覆盖原集合的子集。每个元素必须恰好落入其中一组，不能漏掉，也不能分到两组。

原集合 S
┌─────────┬─────────┬─────────┐
│  子集 1 │  子集 2 │   ...   │
└─────────┴─────────┴─────────┘
每组非空；组间无交集；全部组的并集是 S

幂集 $2^S$ 是“ $S$ 的所有子集构成的集合”，它的元素本身也是集合。若 $|S|=n$ ，每个元素都有选入或不选入子集两种可能，独立组合得到 $|2^S|=2^n$ 。这也是 NFA 转 DFA 时最多出现指数多个状态的原因。

笛卡尔积 $A\times B$ 收集所有有序对 $(a,b)$ ，其中 $a\in A,b\in B$ 。两个位置有各自含义，不能交换。有限时 $|A\times B|=|A||B|$ 。之后让一个状态同时记录两台自动机的状态，使用的就是笛卡尔积。

函数、关系与等价类

函数 $f:A\to B$ 为输入指定唯一输出。全函数对 $A$ 中每个元素都有定义；部分函数允许某些输入没有定义，但一旦有定义，输出仍必须唯一。关系 $R\subseteq A\times B$ 则只说明哪些配对成立，同一个输入可以与多个输出相关联。

集合 $S$ 上的等价关系必须同时满足：自反性 $xRx$ ；对称性 $xRy\Rightarrow yRx$ ；传递性 $xRy\land yRz\Rightarrow xRz$ 。定义 $[x]=\{y\in S:xRy\}$ ，称为 $x$ 的等价类。

自反性保证每个元素都属于某个等价类。若两个等价类有公共元素，结合对称性和传递性可知它们中的元素全都彼此等价，因此两个类其实相同。于是不同的等价类两两不交，所有等价类组成 $S$ 的划分。DFA 最小化将“以后任何输入都无法区分的状态”归为一类，正是这个结构。

图、路径和树

有向图 $G=(V,E)$ 的边是有方向的有序对。标记图还给边附上符号；自动机中的边标签表示读入什么字符。一个 walk 沿相邻边行走，可以重复顶点或边。

本课采用的术语是：path 不重复边，simple path 不重复顶点。前者在其他教材中也可能称为 trail。cycle 从某顶点出发又回到该顶点；simple cycle 除起终点相同外，不重复其他顶点。loop 是一条从顶点指向自身的边。

Euler tour 要把每条边恰好走一次，并回到起点；Hamiltonian cycle 则是经过全部顶点的简单环。两者限制的对象分别是边和顶点。

枚举从某起点出发的所有简单路径时，可以使用回溯：维护当前路径中的顶点集合，只向尚未出现在这条路径上的相邻顶点扩展；返回上一层时，把刚加入的顶点移出集合。

Extend(当前路径 P):
    输出 P
    令 v 为 P 的最后一个顶点
    对 v 的每个相邻顶点 u：
        若 u 不在 P 中：
            把 u 加到 P 末尾
            Extend(P)
            从 P 末尾移除 u

当前路径不重复顶点，所以长度有限；每条简单路径都能沿自身的顶点顺序被扩展出来。这里不能用全局“访问过就永不再进入”的标记，因为同一个顶点可以出现在不同的简单路径中。路径数量本身可能非常大，枚举全部路径的成本不能等同于普通图搜索的线性成本。

树是连通且无环的无向图。指定根后，除根外每个节点有唯一父节点；没有孩子的是叶子。节点深度是根到它的边数，根深度为 0；树高是最大深度。二叉树每个节点至多有两个孩子，高为 $h$ 的二叉树至多有 $2^h$ 个叶子：高度为 0 时只有根；更高的树最多有两棵高度至多 $h-1$ 的子树，叶子数相加至多为 $2\cdot2^{h-1}$ 。

渐近界与证明方法

对最终非负的函数， $f(n)=O(g(n))$ 表示从某个 $n_0$ 开始， $f(n)$ 不超过固定常数倍的 $g(n)$ ； $\Omega$ 表示相应下界； $\Theta$ 表示上下两边都能用固定正常数倍夹住：

\begin{aligned} f=O(g)&\iff \exists c>0,n_0,\ \forall n\ge n_0:\ f(n)\le cg(n),\\ f=\Omega(g)&\iff \exists c>0,n_0,\ \forall n\ge n_0:\ f(n)\ge cg(n),\\ f=\Theta(g)&\iff f=O(g)\text{ 且 }f=\Omega(g). \end{aligned}

若 $f/g$ 的极限为有限非负数，可以推出 $f=O(g)$ ；若极限为正常数，则还可推出 $f=\Theta(g)$ 。但极限不存在，并不代表没有渐近界，最后仍以定义中的不等式为准。

直接证明从前提逐步推出结论；构造证明还要给出满足要求的对象或算法，并验证它确实满足要求。归纳证明用于随长度、规模或结构递增的命题：先证明边界，再假设较小情形成立，推出当前情形。强归纳允许使用所有较小规模；结构归纳则按对象的构造规则分别讨论基本对象与组合对象。

递归定义一个对象，归纳证明关于这个对象的性质，两者作用不同。若一种构造每增加一步都会增加一定数量的组成部分，可以先得到递推，再用归纳证明其闭式。课件中直线划分平面的最大区域数满足 $R(0)=1$ 、 $R(n)=R(n-1)+n$ ，故 $R(n)=1+n(n+1)/2$ ；达到这个最大值需要没有平行线、没有三线共点，使第 $n$ 条直线被分成 $n$ 段，每段新增一个区域。

反证法则暂时假定结论为假，推导出与前提或已知事实冲突的结果。后面的非正则性证明会假设语言可以被某个有限自动机接受，再证明这个假设迫使自动机接受本应拒绝的字符串。

字母表、字符串与空串

字母表 $\Sigma$ 是有限的符号集合。字符串是从这个字母表取出有限多个符号，按顺序排列得到的序列。字符串有顺序，也允许同一符号重复。 $|w|$ 是字符串长度；空串 $\lambda$ 的长度为 0。

连接 $uv$ 表示先写 $u$ ，再写 $v$ ，满足 $|uv|=|u|+|v|$ 、 $u\lambda=\lambda u=u$ 。连接满足结合律，但一般不满足交换律。 $w^k$ 是 $k$ 份 $w$ 的连接， $w^0=\lambda$ 。反转 $w^R$ 把字符顺序倒过来，因此 $(uv)^R=v^Ru^R$ 。

若 $w=uv$ ， $u$ 是前缀， $v$ 是后缀；若 $w=uxv$ ， $x$ 是子串。子串必须连续，前缀和后缀则还固定在两端。它们都可以为空串。

\Sigma^*=\bigcup_{k\ge0}\Sigma^k,\qquad \Sigma^+=\bigcup_{k\ge1}\Sigma^k.

$\Sigma^*$ 包含字母表上的全部有限字符串，包括空串； $\Sigma^+$ 只包含非空字符串。

语言及其运算

语言就是字符串的集合，即 $L\subseteq\Sigma^*$ 。 一个语言可以为空、有限或无限。 $\varnothing$ 没有字符串， $\{\lambda\}$ 有一个长度为零的字符串；集合大小与字符串长度是两个不同的量。

语言可以作并、交、差，补集的全集通常是指定字母表上的 $\Sigma^*$ 。语言连接定义为

L_1L_2=\{uv:u\in L_1,\ v\in L_2\}.

两个成员分别从各自语言独立选择。若定义中的字符串带有某个参数，连接两份语言时，两份所用参数不自动相同。语言反转为 $L^R=\{w^R:w\in L\}$ 。

语言的幂与闭包为

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

$L^*$ 允许连接零份成员，所以必含空串； $L^+$ 至少连接一份成员。如果 $\lambda\in L$ ，取这一份就能得到空串，因此一般不能把 $L^+$ 直接写成 $L^*-\{\lambda\}$ 。只有 $\lambda\notin L$ 时这个等式才成立。还可直接从定义得到 $L\varnothing=\varnothing L=\varnothing$ 、 $L\{\lambda\}=L$ 、 $\varnothing^*=\{\lambda\}$ 。

文法如何生成语言

文法写作 $G=(V,T,S,P)$ ： $V$ 是有限变量集， $T$ 是有限终结符集，两者不交； $S\in V$ 是开始变量； $P$ 是有限产生式集。变量表示尚待展开的结构，终结符构成最终输出字符串。

一般产生式 $\alpha\to\beta$ 中， $\alpha\in(V\cup T)^+$ 是非空串， $\beta\in(V\cup T)^*$ 可以为空；它允许把当前串中出现的一段 $\alpha$ 替换为 $\beta$ 。写 $u\Rightarrow v$ 表示应用一次产生式， $u\Rightarrow^*v$ 表示应用零次或多次。由开始符号推出的中间串叫句型，可能同时含变量与终结符；全部由终结符组成的结果才属于生成语言：

L(G)=\{w\in T^*:S\Rightarrow^*w\}.

开始变量 S → 含变量的句型 → 继续展开 → 纯终结符字符串
                    尚未完成              属于 L(G)

证明一个文法恰好生成目标语言，也需要两个方向：每次产生式应用都保持目标结构，证明它不会生成非法字符串；再说明每个目标字符串都能按某种分解方式被生成，证明它不会漏掉合法字符串。只展示几次成功推导不能代替第二个方向。两个文法等价，是指它们生成的语言相同，产生式和推导过程可以不同。

Lec 2：有限自动机如何记住已经读过的信息

DFA 的状态与接受条件

有限自动机逐个读入字符，用当前状态保存与未来判断有关的信息。DFA 是确定性有限接受器，定义为

M=(Q,\Sigma,\delta,q_0,F).

$Q$ 是有限状态集， $q_0$ 是初态， $F\subseteq Q$ 是接受状态集， $\delta:Q\times\Sigma\to Q$ 是全函数。每个状态对每个输入字符都必须有且只有一个后继状态。转移图中起始箭头指向 $q_0$ ，双圈表示接受状态，带字符的箭头表示转移。

已经读完的前缀 u       下一个字符 a
         │                  │
         ▼                  ▼
      当前状态 q ── δ(q,a) ──→ 新状态

扩展转移函数把一次读一个字符扩展为读完整个字符串：

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

于是 $L(M)=\{w:\delta^*(q_0,w)\in F\}$ 。必须读完整个输入，最后处于接受状态才算接受。 中途经过双圈并不自动结束。空串没有字符可读，因此它被接受当且仅当 $q_0\in F$ 。

陷阱状态通常指进入后再也不能到达接受状态的拒绝区域，常被表示为对所有字符自环的一个拒绝状态。它不会让机器跳过“读完输入”的定义，只是之后的字符已无法改变拒绝结果。若图省略了某些 DFA 转移，应补到这样的状态，才能得到完整 DFA。

状态设计：只保留未来还需要的信息

若两个已读前缀在接上任意相同后缀后，总是一起被接受或一起被拒绝，就没有必要用不同状态区分它们。反之，只要某个后缀能使结果不同，就必须留下区别。状态的含义应在画转移之前确定；每条转移都要能根据这个含义解释。

常见的有限信息有三类。计数只关心模 $d$ 的余数时，保存 $0,\ldots,d-1$ 即可；读到需要计数的字符，就把余数加 1 后取模。若只关心是否达到某个固定次数，可以保存达到阈值前的精确计数，再用一个状态表示“已达到”或“已超过”，具体含义由条件决定。若读取数字串的数值模 $d$ ，当前余数为 $r$ ，读入一个 $b$ 进制数字 $a$ 后，新余数为 $(br+a)\bmod d$ 。

匹配固定模式串 $p$ 时，可以保存“已读串的后缀与 $p$ 的前缀相符的最大长度”。读入新字符后，重新找仍然匹配的最长后缀。这能处理模式间重叠，不会因为一次失配就错误地丢掉仍可用的结尾。若条件是包含模式，一旦完整匹配，以后都可保持接受；若条件是禁止包含模式，一旦出现就永久拒绝；若条件是以模式结尾，即使刚匹配成功，也必须继续更新，因为后续字符会改变结尾。

指定开头的固定前缀条件则有不同的转移规则：逐位匹配前缀，任何一次失配都永久拒绝；完整匹配后，后续字符不再改变“具有这个前缀”的事实，可以留在接受状态。

多个条件需要同时记录时，状态可设成一个有序对或元组，各分量分别更新。这样得到有限个组合状态。最终接受条件再根据“并且”“或者”等逻辑关系决定。Lec 4 的乘积自动机会把这个办法正式写出。

NFA 的一条成功路径意味着什么

NFA 允许同一状态、同一输入字符有多个后继，也允许没有后继；还允许不消耗输入字符的 $\lambda$ 转移。其转移函数为

\delta:Q\times(\Sigma\cup\{\lambda\})\to2^Q.

返回值是状态集合。空集表示这一支没有可走的边； $\lambda$ 是空串标记，不是输入带上的额外字符。NFA 接受一个字符串，要求至少存在一条读完整个输入并到达接受状态的运行路径。某条路径失败不会否定另一条成功路径；只有所有可能路径都不能接受，才拒绝。

这种“存在一条路径”是数学定义，不是随机挑一条路径运行。实现时可以同时追踪所有可能状态，避免猜错路径。

空串闭包与 NFA 模拟

对状态集合 $S$ ，定义 $E(S)$ 为从 $S$ 中任一状态出发，只走零条或多条 $\lambda$ 边能到达的全部状态。零条边允许原状态留在结果里。计算时用图搜索，只沿 $\lambda$ 边扩展；已访问的状态不再重复处理，所以空串环也不会导致无限搜索。

NFA 的扩展转移 $\delta^*(q,w)$ 表示从 $q$ 出发，恰好读完 $w$ 后能到达的全部状态；其中 $\delta^*(q,\lambda)=E(\{q\})$ 。它返回一个状态集合，与 DFA 的单一状态返回值不同。

读入字符 $a$ 的过程是：先在当前可能状态中取所有标为 $a$ 的后继，再求这些后继的空串闭包。

S_0=E(\{q_0\}),\qquad S_{t+1}=E\left(\bigcup_{q\in S_t}\delta(q,a_{t+1})\right).

当前所有可能状态（已做空串闭包）
                  │ 恰好读入一个字符 a
                  ▼
           所有 a 边的终点
                  │ 走任意多条空串边
                  ▼
           下一组所有可能状态

初态先做闭包，保证读第一个字符之前可以走空串边；每次读字符之后再做闭包，保证字符之间及输入结束后的空串转移都被纳入。最终若 $S_{|w|}\cap F\ne\varnothing$ 就接受。这个集合与 $F$ 相交即可，不要求里面所有状态都接受。

子集构造：把整组可能状态看成一个 DFA 状态

NFA 模拟中的集合变化其实是确定的：给定当前集合和输入字符，下一集合唯一。因此可把每个出现的状态集合直接当作新 DFA 的一个状态。

SubsetConstruction(NFA):
    DFA 初态 A0 = E({q0})
    把 A0 放进待处理队列
    当队列非空：
        取出一个集合 A
        对每个输入字符 a：
            B = E(所有 q∈A 的 δ(q,a) 的并集)
            记录 DFA 转移 A --a--> B
            若 B 尚未建立：建立 B 并入队
    将所有与 NFA 接受集 F 相交的集合标为接受状态

空集合也可能出现，它读任意字符后仍为空，是新 DFA 的拒绝陷阱。 $k$ 个 NFA 状态最多有 $2^k$ 个子集，所以构造一定结束；实际只建立可达子集，常常少于这个上界。

正确性可对已读前缀的长度归纳：初始集合恰好是未读字符时 NFA 能到达的状态；假设当前集合恰好收集全部可能状态，读取下一字符并取闭包就恰好收集全部新可能状态。因此，读完整串后，新 DFA 接受当且仅当原 NFA 有一条接受路径。这证明 NFA 与 DFA 接受同一类语言，即正则语言。

有时构造需要 NFA 只有一个接受状态。可以增加新状态 $f$ ，从每个旧接受状态向 $f$ 加一条 $\lambda$ 边，取消所有旧接受标记，只把 $f$ 设为接受态，并让 $f$ 没有出边。这样仍可在任一旧接受位置完成接受。若原来没有接受状态，新 $f$ 不可达，语言仍为空。这个操作使用空串边，因此得到的是 NFA。

DFA 最小化：合并真正不可区分的状态

两个状态 $p,q$ 等价，指对每个后缀 $z\in\Sigma^*$ ，从它们开始读 $z$ 的接受结果都相同：

p\sim q\iff \forall z\in\Sigma^*,\quad \delta^*(p,z)\in F\Longleftrightarrow\delta^*(q,z)\in F.

若某个 $z$ 使一方接受、一方拒绝， $z$ 就是区分它们的后缀。空串已经能区分接受态与非接受态，因此两类一开始就必须分开。

最小化先删去从初态不可达的状态，再不断细分划分。最初按接受与否分成至多两组。对于同组内的状态，比较它们对每个字符的转移落入哪一组；只要某个字符导致它们进入不同组，就把它们拆开。重复直到没有组需要继续拆分。

初始分组：接受状态 | 非接受状态
                  ↓
按各字符的后继所在组继续拆分
                  ↓
直到同组状态的全部转移都进入相同的组
                  ↓
每组缩成一个状态，得到最小 DFA

每次拆分都有理由：后继已能被某个后缀区分，那么在这个后缀前加上当前字符，就能区分原状态。反过来，稳定以后，同组状态首先具有相同接受性，读一个字符后又进入同一组；对后缀长度归纳，任何后缀都无法区分它们，所以合并正确。

商自动机的状态就是这些组，初态为原初态所在组，接受组由接受态组成，转移由任一代表状态决定。稳定性保证选哪个代表都进入同一组。不同可达组之间存在区分后缀，任何等价 DFA 都必须把它们分开，因此这个结果确实最小。

Lec 3：正则表达式、自动机与正则文法的转换

正则表达式的语法和含义

正则表达式用有限的式子描述语言。基本表达式为 $\varnothing$ 、 $\lambda$ 和任意单个字符 $a\in\Sigma$ ；已有表达式 $r,s$ 可以组合成 $r+s$ 、 $rs$ 和 $r^*$ ，分别表示选择、连接与重复零次或多次。优先级从高到低是星号、连接、并，括号可改变结合范围。

表达式是一个描述，语言是它描述的字符串集合，二者用 $L(r)$ 联系：

\begin{aligned} L(\varnothing)&=\varnothing,&L(\lambda)&=\{\lambda\},&L(a)&=\{a\},\\ L(r+s)&=L(r)\cup L(s),&L(rs)&=L(r)L(s),&L(r^*)&=L(r)^*. \end{aligned}

两个表达式等价，指它们描述同一个语言，不要求文本相同。由语言运算可得 $r+\varnothing=r$ 、 $r\lambda=\lambda r=r$ 、 $r\varnothing=\varnothing r=\varnothing$ 、 $\varnothing^*=\lambda$ 。这里的等号表示语言等价。连接一般不能交换次序，并运算则可以。

构造表达式时，应先把语言的完整字符串拆成有限个分支、先后部分或可重复片段。每个分支要包含它允许的全部长度，空串是否合法也要由定义决定。若条件需要记忆多个状态，可以先构造自动机，再机械地转成表达式；不必靠猜一个复杂式子完成描述。

表达式转 NFA：按表达式结构组合机器

为每个子表达式建立一个有独立入口和出口的 NFA 片段，入口不被片段内边指入，出口没有片段内出边。基本片段中， $\varnothing$ 的入口到出口无路， $\lambda$ 用一条空串边连接，字符 $a$ 用一条标 $a$ 的边连接。

并运算建立新入口、新出口。新入口用空串边分别连到两个子片段入口，两个出口再用空串边汇入新出口。任一成功路径选择其中一边，因此接受语言是并集。

               ┌─λ─ [ r 的片段 ] ─λ─┐
新入口 ────────┤                     ├── 新出口
               └─λ─ [ s 的片段 ] ─λ─┘

连接把 $r$ 的出口用空串边连到 $s$ 的入口，只保留整体入口和最终出口的角色。任一接受路径先完整读入一个属于 $L(r)$ 的字符串，再读入一个属于 $L(s)$ 的字符串，因此实现 $L(r)L(s)$ 。

星号增加新入口、新出口；入口可直接走空串边到出口，表示重复零次；也可进入子片段。子片段出口既可到新出口，也可回到子片段入口继续重复。

s --λ--> i --[r]--> o --λ--> f
         ^          |
         +-----λ----+

零次路径：s --λ--> f

图中 $s,f$ 是新入口和新出口， $i,o$ 是子片段的入口和出口， $[r]$ 代表子表达式 $r$ 对应的片段。

由基本片段的正确性，以及三种组合恰好实现对应语言运算，可按表达式结构归纳得到：任意正则表达式都能转成等价 NFA。每次组合只增加常数个节点和连接，构造出的 NFA 大小与表达式语法树大小成线性关系。

自动机转表达式：消去状态但保留路径含义

广义转移图 GTG 允许边标签是正则表达式。一条边代表可以读入标签语言中的任意字符串。两点之间原有多条边时，把标签取并；没有边时用 $\varnothing$ 表示。这样可以为每对状态统一维护一个表达式 $R_{ij}$ 。

先增加一个没有入边的新初态 $s$ ，用 $\lambda$ 边指向原初态；增加一个没有出边的新终态 $f$ ，所有旧接受态用 $\lambda$ 边指向它，并取消旧接受标记。这也处理了原初态本身接受空串的情形。

若要删去中间状态 $k$ ，一条从保留状态 $i$ 到保留状态 $j$ 的路径，要么不经过 $k$ ，要么先到 $k$ ，在 $k$ 绕零圈或多圈，再离开到 $j$ 。因此对全部 $i,j\ne k$ 同时更新：

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

原来已有：i ───────── Rij ─────────→ j

经过 k ： i ─ Rik → k ─ Rkj ──────→ j
                    ↻ Rkk

删去 k 后，把两种路径的语言取并

每轮右侧应使用删除 $k$ 之前的标签，不能边更新边把新标签当作旧值继续代入。随后删除 $k$ 和相连的边，再消去下一个中间状态。最终只剩 $s,f$ ，从 $s$ 到 $f$ 的标签就是所求表达式。因新初态没有入边、新终态没有出边，不再需要额外处理两端自环。

这个过程保持的不变式是：当前边标签准确概括了原图中、内部只经过已删除状态的路径语言。每次消元加入经过新删除状态的全部方式，因此既不漏路径，也不制造原图没有的路径。消元顺序可能改变表达式大小与外观，但不会改变语言；表达式本身可能增长得很大，不能只凭状态有有限个就声称输出一定很短。

两个转换方向合起来证明 Kleene 定理：DFA、NFA 和正则表达式描述的恰好是同一类正则语言。

正则文法为什么相当于有限状态转移

线性文法要求每条产生式右边至多有一个变量。右线性文法进一步要求变量若存在，就必须位于最右端，产生式形如 $A\to uB$ 或 $A\to u$ ，其中 $u$ 是终结符串。左线性文法则形如 $A\to Bu$ 或 $A\to u$ 。

正则文法要求整套规则统一为右线性或统一为左线性。仅仅保证每条规则至多一个变量，还不足以保证正则性；把左线性和右线性规则任意混用，也不再属于这个定义。

右线性文法转 NFA 时，为每个变量建立一个状态，开始变量对应初态，再增加最终接受状态 $f$ 。规则 $A\to a_1\cdots a_kB$ 变成从 $A$ 到 $B$ 、依次读入这些字符的路径，必要时增加中间状态。规则 $A\to a_1\cdots a_k$ 的路径终点则是 $f$ 。终结符串为空时，使用空串边。

文法：A → uB          自动机：A ──读入 u──→ B
文法：A → u           自动机：A ──读入 u──→ f

每次推导在已生成终结符后面保留一个待展开变量；每次自动机转移恰好读入同样的终结符，并走到这个变量的状态。推导在纯终结符串结束，当且仅当路径到达 $f$ ，所以两者语言相同。

反方向，把 NFA 状态当作变量。每条 $q\xrightarrow{a}p$ 产生规则 $q\to ap$ ；空串边产生 $q\to p$ ；每个接受态 $q$ 再增加 $q\to\lambda$ 。从初态变量开始推导，便能复现一条接受路径。

左线性文法可先反转每条右侧： $A\to Bu$ 改成 $A\to u^RB$ ， $A\to u$ 改成 $A\to u^R$ 。所得右线性文法生成原语言的反转。把它转为 NFA，再反转自动机的边并交换起终角色，就得到原语言的 NFA。由此，正则文法也与前三种表示等价。

正则表达式 ⇄ NFA ⇄ DFA
                ⇅
             正则文法

转换改变表示方式，保持被接受或被生成的字符串集合

Lec 4：正则语言的封闭性、判定算法与局限

封闭性说明运算后仍能构造有限自动机

一种语言类对某运算封闭，意思是把这个运算用于类中的语言，结果仍属于这个类。证明正则语言的封闭性，最直接的办法是给出对应自动机的构造，并说明它接受的恰好是运算结果。

并、连接和星号可以使用上一讲组合 NFA 的三种方法。并让新初态选择进入哪台机器；连接让前一台接受后接入后一台；星号允许走零次，也允许在完成一次后再次进入。每条接受路径分别对应选择一个分支、连接两个成员、连接有限多个成员，因此语言含义完全对应。

反转语言时，把原 NFA 的每条边反向，增加一个新初态，用空串边连到所有旧接受态，把旧初态设为唯一接受态。原来读 $a_1\cdots a_k$ 的接受路径，倒过来就读 $a_k\cdots a_1$ ；反过来每条新接受路径也对应旧路径的反转。这证明 $L^R$ 正则。

补集使用同一字母表上的完整 DFA，把接受态与非接受态互换即可。因为每个输入恰有一条完整运行，它原先接受就变为拒绝，原先拒绝就变为接受。NFA 有多条运行路径，互换标记只改变各条路径的终点性质，无法把“存在接受路径”变成“完全没有接受路径”，所以不能用同样操作直接给 NFA 求补。

乘积自动机实现交、并和差

设两台完整 DFA 的状态分别为 $p,q$ 。新状态 $(p,q)$ 同时记录它们读过同一个前缀后的状态。初态为 $(q_{01},q_{02})$ ，每个字符 $a$ 的转移为

\delta((p,q),a)=(\delta_1(p,a),\delta_2(q,a)).

                 同一个字符 a
                      │
              ┌───────┴───────┐
              ▼               ▼
机器 1：p → δ₁(p,a)   机器 2：q → δ₂(q,a)
              └───────┬───────┘
                      ▼
              新的组合状态

最后只需改变接受条件：交集要求两分量都接受；并集要求至少一个接受；差集 $L_1-L_2$ 要求第一分量接受且第二分量拒绝；对称差要求恰好一个接受。对输入长度归纳，新状态的两分量始终与原机器的真实状态一致，因此这些接受条件恰好实现相应语言运算。

新状态最多有 $|Q_1||Q_2|$ 个，只需建立从初态可达的组合。它说明封闭性不仅是一条可背诵结论，也给出了可执行构造。交集还可由德摩根律和补集、并集的封闭性推出；差集等于 $L_1\cap\overline{L_2}$ 。

同态：固定地替换每个字符

同态 $h:\Sigma\to\Gamma^*$ 为每个原字符指定一个固定的目标字符串，再逐字符连接：

h(a_1\cdots a_k)=h(a_1)\cdots h(a_k),\qquad h(\lambda)=\lambda.

同一个字符每次出现都按相同规则替换，某个替换串可以为空。语言的同态像为 $h(L)=\{h(w):w\in L\}$ 。

若 $L$ 正则，可在它的正则表达式中把每个字符 $a$ 替换为描述 $h(a)$ 的表达式；或者在 NFA 中把每条字符边替换成读入整个 $h(a)$ 的路径。原来的每条接受路径便准确变成被逐字符替换后的路径，所以 $h(L)$ 仍正则。

四个判定问题及其算法

给出语言的自动机、正则表达式或正则文法，是给出一种有限表示；算法处理的是这个表示，而不是把无限语言的成员逐个列出。必要时先转换为 DFA，以下步骤描述得到 DFA 之后的判定。

成员问题问给定字符串 $w$ 是否属于语言。保存当前状态，从初态逐字符应用 $\delta$ ，读完检查是否在 $F$ 。对固定 DFA，这需要 $O(|w|)$ 时间和常数个当前状态的存储。

空语言问题问是否存在任何被接受的字符串。从初态做图搜索，检查能否到达某个接受态。可达路径上的标签给出一个被接受的串；如果没有这样的路径，就没有任何输入能够被接受。搜索时间为状态数加转移数。

有限性问题问接受的不同字符串是否有无穷多个。先保留从初态可达、且还能到达某个接受态的状态；这些是可能位于成功运行上的状态。在其诱导子图中检测有向环。若有环，就可以先进入环、绕任意多圈、再到接受态。在 DFA 中每条边消耗一个字符，每多绕一圈会增加正长度，因此得到无限多个不同字符串。若没有环，成功运行不能重复状态，长度有统一上界；有限字母表上有界长度的字符串只有有限个，所以语言有限。

初态 ──可达──→ 环 ──可达──→ 接受态
                ↻
       环必须位于某条成功运行上

图中任意一处有环并不足够：不可达的环、无法通向接受态的环，都不会产生无限多个被接受的串。若直接处理带空串边的 NFA，还要保证循环能消耗正长度输入；纯空串环不会增加字符串长度。先转成 DFA 可避免这个额外区分。

等价性问题问 $L_1=L_2$ 是否成立。构造接受对称差

(L_1-L_2)\cup(L_2-L_1)

的乘积 DFA，再检查其语言是否为空。如果为空，两台机器对每个字符串的结果都一致；如果非空，从初态到接受态的路径就给出一条使两者结果不同的字符串。这是完整判定方法，比较几条测试字符串不能替代它。

泵引理从有限状态的重复中产生

设一个 DFA 有 $p$ 个状态。读入一个长度至少为 $p$ 的字符串时，只看前 $p$ 个字符，就会经过包括初态在内的 $p+1$ 次状态位置。根据抽屉原理，至少两次位置对应同一状态。

把第一次到这个状态之前读入的部分记为 $x$ ，两次出现之间记为 $y$ ，剩余部分记为 $z$ 。于是 $w=xyz$ ， $|xy|\le p$ ，且 $|y|>0$ 。读 $y$ 会从同一状态出发再回到同一状态，所以可以不读它、读一次或读任意多次，随后照常读 $z$ 。

初态 ── x ──→ q ── z ──→ 接受态
              ↻ y

xy⁰z、xy¹z、xy²z、... 都沿同一入口和出口完成接受

因此，每个正则语言都满足：存在整数 $p\ge1$ ，对每个 $w\in L$ 且 $|w|\ge p$ ，存在分解 $w=xyz$ ，使

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

有限语言也满足这个表述，只要 $p$ 大于所有成员长度，前提中便没有需要考虑的长字符串。引理的实质是正则语言的必要条件；满足它本身不能推出正则性。

用泵引理证明非正则时，谁能选择什么

要证明非正则，必须否定刚才那一整句，而不是找一条“看起来不能重复”的字符串。正确的选择顺序是：

假设 $L$ 正则，取它所保证的某个泵长度 $p$ 。 $p$ 的具体值未知。
根据这个 $p$ 选一条确定属于 $L$ 、长度至少为 $p$ 的字符串 $w$ 。
考虑所有满足 $w=xyz$ 、 $|xy|\le p$ 、 $|y|>0$ 的分解。
对每种这样的分解，找某个 $t\ge0$ ，证明 $xy^tz\notin L$ 。 $t$ 可以依赖这次分解。

其中第 3 步不能自行指定 $y$ 恰好是哪一段。可以利用长度条件推出所有合法 $y$ 必须具有的性质，之后的论证必须覆盖这些可能性。

若 $w$ 前 $p$ 个字符全属于同一段，那么 $y$ 必在这一段内。设 $|y|=d$ ，则 $1\le d\le p$ 。重复后，这一段长度改变 $(t-1)d$ ，其他段不变。需要检查这个变化究竟破坏了语言要求中的什么：是两段数量关系、符号排列顺序、镜像对应，还是允许长度的算术条件。

对于只限制长度的语言，泵后长度为 $|w|+(t-1)d$ 。如果合法长度间的空隙足够大，就可以让所有 $1\le d\le p$ 的变化都落在非法间隔内；如果条件涉及整除性，则可能需要根据 $d$ 选择重复次数。每一步都必须给出明确的不等式或整除关系，不能仅说“重复后不满足”。

封闭性和可区分前缀提供另外两条证明路线

封闭性证明可以反向使用。先假设待证语言 $L$ 正则，再对它做已证明保持正则性的运算，得到一个已经证明非正则的语言，便产生矛盾。常用做法是与一个正则语言求交来限制排列形式，取补集后再求交，或通过同态删除、合并某些字符。必须明确每个辅助语言为何正则，以及运算结果为什么恰好是目标语言。

可区分前缀则直接利用状态有限。若能找出无限多个前缀，并证明任意两个不同前缀都存在一个共同后缀，使接上后一个属于 $L$ 、另一个不属于 $L$ ，那么这些前缀必须到达不同状态。否则从同一状态读相同后缀会得到相同结果，产生矛盾。无限多个必须区分的前缀需要无限多个状态，所以不存在接受该语言的 DFA。

这两条路线与泵引理具有相同根源：有限状态能够记忆的区别有限。选择哪条路线，应由语言条件的结构决定。

Lec 5：上下文无关文法、语法树与歧义

CFG 的规则允许表达递归结构

上下文无关文法 CFG 仍写作 $G=(V,T,S,P)$ ，但每条产生式左侧必须恰好是一个变量：

A\to\alpha,\qquad A\in V,\quad\alpha\in(V\cup T)^*.

“上下文无关”表示，只要当前句型出现变量 $A$ ，就可以把它替换为 $\alpha$ ，不需要检查左右邻居。右侧可以含多个变量，也可以为空。一个语言是上下文无关语言 CFL，指存在某个 CFG 生成它。正则文法属于 CFG，所以每个正则语言也是 CFL。

递归规则可以在一次展开中同时决定两侧结构。形如 $S\to aSb$ 的规则，每应用一次就在内部结果两端各加一个指定符号；以 $S\to\lambda$ 结束时，两侧数量相等，且全部 $a$ 在全部 $b$ 之前。形如 $S\to aSa$ 的规则则在两侧加入相同字符，配合可选择的终结符和合适的终止规则，可以表达镜像结构。空串终止对应偶数长度，单字符终止对应奇数长度。

多个变量或 $S\to SS$ 还允许连接两个独立生成的结构。以左括号、右括号代替 $a,b$ ，规则

S\to aSb\mid SS\mid\lambda

表达嵌套、并列和空结构。它生成的括号串必须满足：总左括号数等于总右括号数，而且任何前缀中左括号数都不少于右括号数。后一条件保证读到右括号时前面确实有尚未匹配的左括号，仅有总数相等并不够。

这组规则的完整性来自合法括号串的递归分解：一个非空合法串的第一个左括号有唯一匹配的右括号，二者之间是一段合法括号串，之后又是一段合法括号串。因此能先生成嵌套部分，再与后续部分连接。若还允许规则 $S\to bSa$ ，则可生成两类符号总数相等、却不一定满足括号前缀条件的串。顺序约束与数量约束必须分别说明。

推导顺序与语法树记录的是不同信息

当句型中有多个变量时，可能先展开左边，也可能先展开右边。最左推导规定每次展开最左侧变量，最右推导规定每次展开最右侧变量。这些规则固定的是展开顺序，不改变文法可以生成的语言。

语法树记录每个变量使用了哪一条产生式。根为开始变量，内部节点为变量；若节点标记为 $A$ ，其孩子从左到右必须恰好组成某条 $A\to\alpha$ 的右侧。完整树的叶子是终结符或空串标记；空串产生式对应一个单独的 $\lambda$ 孩子。按从左到右读取叶子、忽略空串，就得到树的 yield，即生成字符串。

                    A
              /     │      \
            α₁      α₂      α₃
             │       │       │
          各自按规则继续展开
                    ↓
       从左到右读取全部叶子，得到字符串

部分语法树允许叶子仍有变量，表示推导尚未完成。以 $S$ 为根时，叶子序列就是一个句型。给定完整树，按最左未展开变量的顺序展开，可以得到唯一的最左推导；按最右顺序也有唯一的最右推导。它们虽然步骤先后不同，却可能对应同一棵树。

歧义是同一个字符串具有不同结构

一个 CFG 有歧义，指存在某个 $w\in L(G)$ ，它有两棵不同的语法树。等价地，它有两份不同的最左推导，或两份不同的最右推导。仅有两份普通推导不够，因为它们可能只是展开顺序不同，实际仍是同一棵树。

表达式文法若把各种运算都放在同一层，便可能让同一串符号具有不同的运算分组。规定优先级时，可把表达式分为不同层：

\begin{aligned} E&\to E+T\mid T,\\ T&\to T*F\mid F,\\ F&\to(E)\mid a. \end{aligned}

$E$ 是加法层， $T$ 是乘法层， $F$ 是原子或括号。乘法必须先在一个 $T$ 内形成，才能作为加法的一项，因此优先级被写进树的结构。 $E\to E+T$ 让连续加法沿左侧递归展开，对应左结合；括号通过 $F\to(E)$ 把完整表达式包成一个原子，允许显式改变分组。去歧义需要这样的结构约束，不能只在文法外口头说“先算乘法”。

条件语句的 dangling else 也是结构问题：一个 else 可能被接到不同层次的 if。语言规范必须确定绑定规则，文法或解析器再实现该规则。它与表达式优先级相同，都是为了让同一程序具有确定的语法结构。

文法有歧义不代表语言固有歧义。固有歧义是语言层面的性质：生成这个语言的每个 CFG 都有歧义。找出某一份文法的两棵树，只能证明这一份文法有歧义，不能证明所有等价文法都无法消除歧义。

从生成转向解析

生成从 $S$ 出发逐步得到字符串；解析则给定字符串 $w$ ，寻找它的推导或语法树。成员判定只需回答是否存在，解析还要输出一份结构。

穷举解析可以逐层枚举最左推导：从 $S$ 开始，对每个句型尝试最左变量的所有产生式，再进入下一层。使用最左推导不会漏掉任何可生成字符串，因为每棵语法树都有对应的最左推导。若找到 $w$ 就成功；但一般文法可能有空串规则、单位规则或递归环，使无解输入上的搜索永远没有自然停止点。

如果文法没有 $A\to\lambda$ 和 $A\to B$ ，则可给出有限深度界。目标长度为 $n\ge1$ 时，每步规则要么让句型长度至少增加 1，要么是 $A\to a$ ，将一个变量变成终结符。前一类最多 $n-1$ 次，后一类最多 $n$ 次，所以任何成功推导最多 $2n-1$ 步。超过该深度仍未成功就可以拒绝；长度超过 $n$ 的句型也可立即剪去。空输入则在此规则限制下直接拒绝。

有限停止并不等于高效。若每次展开有多种选择，推导树的分支会随深度成指数增长。这正是需要 CYK 等动态规划算法的原因。

s-grammar 为什么可以不回溯地解析

s-grammar 的每条规则形如 $A\to a\alpha$ ，其中 $a$ 为终结符、 $\alpha$ 是变量串，并且给定一对 $(A,a)$ ，最多只有一条规则。最左变量是 $A$ 、下一个输入字符是 $a$ 时，产生式已经被唯一确定。

解析器用栈保存待展开变量，开始时压入 $S$ 。每次取出栈顶 $A$ ，看下一个输入字符 $a$ ；若不存在对应规则则拒绝，否则消费 $a$ ，把右侧变量串按反向压栈，使其最左变量下次先处理。输入与栈必须同时耗尽才接受。

每步消费恰好一个字符，规则没有分支选择。对固定文法，右侧长度有固定上界，所以长度为 $n$ 的输入可在线性时间完成解析。GNF 也要求规则以终结符开头，但它不额外保证 $(A,a)$ 唯一；两者的确定性能力不能混同。

文法在编译中的作用

编译器的词法分析把字符序列识别为标识符、关键字、运算符等 token；语法分析根据文法把 token 组织成树；后续语义分析检查类型、声明等语法结构之外的条件，代码生成再把有效结构转换为目标指令。

源代码字符 → 词法分析 → token 序列 → 语法分析 → 语法树
                                                   │
                                      语义检查、后续处理
                                                   ▼
                                               目标代码

BNF 是表达产生式的一种常用记法，::= 表示定义，| 表示候选规则。LL、LR 文法支持专门的高效解析方法；这里的结论不意味着任意 CFG 都可以用同一种线性算法解析。一个串符合语法，也不保证类型和运行含义正确，语法与语义分别处理不同问题。

Lec 6：整理文法并用 CYK 判断成员

等价变换要保留所有可能的推导

这里使用的替换定理要求 $A$ 与 $B$ 是不同变量。若有产生式 $A\to uBv$ ，且 $B$ 的全部规则为 $B\to\beta_1\mid\cdots\mid\beta_k$ ，可以把这一条 $A$ 规则替换为

A\to u\beta_1v\mid\cdots\mid u\beta_kv.

原来先展开 $A$ 、再展开这个 $B$ 的两步被合成一步；反过来，每条新规则也能展开回原来的两步，因此生成语言不变。删除旧规则时必须包含 $B$ 的全部候选；若只展开其中一个候选，则只能把新规则作为补充，不能无故删去其他路径。以下清理过程都依据这种“省去中间推导、保留最终字符串”的思想。

删除空串产生式：先找出全部 nullable 变量

变量 $A$ 可空，表示 $A\Rightarrow^*\lambda$ ，不要求它直接有 $A\to\lambda$ 。因此先计算一个集合 $N$ ：初始放入所有直接产生空串的变量；之后反复扫描规则，若某条右侧全部由已在 $N$ 中的变量组成，就把它的左侧变量也加入 $N$ ，直到不再增加。含终结符的右侧不能消成空串。

这个过程求得全部可空变量。每次加入的变量确实能让右侧所有部分消失，所以不会误加；任意能够推出空串的有限语法树，从叶部向上看，节点会依次被加入，因此不会遗漏间接可空的变量。

对每条规则，枚举右侧每一个可空变量出现位置的“保留或删除”，加入得到的所有非空右侧，再删掉原空串规则。选择单位是出现位置，不是变量名称。 同一个可空变量在右侧出现两次，两次可以分别消失。

右侧中的每个可空位置
        ├── 保留：由它生成非空部分
        └── 删除：代替原推导中生成空串的情形

组合所有选择，再去除重复规则

新规则模拟的是原推导中某些子树生成空串的情况；反过来，任何被删除的位置都可以在原文法中补上生成空串的子树。所以变换保留所有非空成员。

若原语言还包含空串，需要另外保留它：先增加一个从未出现在任何右侧的新开始符号 $S_0$ ，让它能开始原来的推导，并保留 $S_0\to\lambda$ 。后续清理会消除 $S_0\to S$ 这条单位规则，但空串规则作为唯一的起始例外留下。让 $S_0$ 不出现在右侧，避免它的可空性再次影响内部规则。

若一条右侧有 $r$ 个可空出现位置，直接枚举可能产生最多 $2^r$ 种组合。算法的可行性与规则数增长要分开看，不能把所有文法变换一概视为线性操作。

删除单位产生式：计算可达闭包再复制出口

单位产生式是 $A\to B$ ，右侧恰好一个变量。若连续使用单位规则，推导只是在变量之间换名，没有产生终结符，也没有分裂结构。

建立有向图，每条单位规则对应一条边。对每个 $A$ ，求出沿零条或多条单位边能到达的变量集合 $U(A)$ ，其中包括 $A$ 自身。对于每个 $B\in U(A)$ ，把 $B$ 的全部非单位规则 $B\to\alpha$ 复制为 $A\to\alpha$ 。完成所有复制后，删除全部单位规则。

A ─单位规则→ ... ─单位规则→ B ─非单位规则→ α
                         ↓
                  直接加入 A → α

新规则把“走一串单位边后终于做一次实质展开”合成一步，所以保留原语言。单位规则形成环时，图搜索的访问标记保证终止；不需要无止境地展开 $A\to B\to A$ 。若存在开始符号的空串例外，应在这一过程中一并保留。

删除无用符号：先能完成，再能到达

一个变量真正有用，要求它能出现在某个从 $S$ 到纯终结符串的完整推导中。这包含两种要求：它能生成某个纯终结符串，称为 generating；它能在从开始符号出发的推导中出现，称为 reachable。仅满足一项还不够。

先求 generating 集合。初始加入具有纯终结符右侧的变量；之后若某条规则右侧的所有变量都已经 generating，就把左侧加入。达到固定点后，删除所有非 generating 变量以及包含它们的规则。若开始变量也不 generating，语言为空，可以直接保留一个没有可用产生式的开始变量作为空语言表示。

接着在删减后的文法中求 reachable。从 $S$ 开始，若可达变量的规则右侧出现某变量，就把它标为可达，直到没有新增。再删除不可达变量及其规则。顺序不能颠倒，因为删去无法完成的规则后，原先形式上可达的变量可能已失去唯一入口。

原文法
  │ 删除不能生成纯终结符串的部分
  ▼
剩余文法
  │ 从开始变量重新查可达性
  ▼
只保留能参与完整成功推导的部分

整体清理通常按“空串规则、单位规则、无用部分”进行。原因是删除空串规则可能产生新的单位规则，前两种变换也可能留下新的无用部分。按这个次序处理，最后得到的规则才能同时满足目标限制。

Chomsky 标准形 CNF

CNF 的非空产生式只有两种：

\boxed{A\to BC\quad\text{或}\quad A\to a.}

$A,B,C$ 都是变量， $a$ 是一个终结符。若语言包含空串，可以保留唯一例外 $S_0\to\lambda$ ，且 $S_0$ 不出现在右侧。除此之外，不允许单位规则、长右侧、两个终结符的右侧或变量与终结符混排。

转换先完成前述清理。然后只在长度至少为 2 的右侧中，用新变量 $T_a$ 替换终结符 $a$ ，并加入 $T_a\to a$ 。原来合法的单字符规则 $A\to a$ 直接保留，不必再变成单位规则。

此时长右侧只含变量。把 $A\to C_1\cdots C_k$ 、 $k\ge3$ 改成二元链：

A\to C_1Z_1,\quad Z_1\to C_2Z_2,\quad\ldots,\quad Z_{k-2}\to C_{k-1}C_k.

这些 $Z$ 是新变量，使用时避免与其他规则的辅助变量混淆。沿链展开会恢复原来的变量串；反过来，原长规则可以用这条链模拟，所以语言不变。

一条长规则：A → C₁ C₂ ... Cₖ

二元化后： A
          / \
        C₁   Z₁
            /  \
          C₂    Z₂
                 ...

CNF 把非空语法树的分叉统一为二叉结构。生成长度为 $n\ge1$ 的串时，有 $n$ 次变量到终结符的规则，以及 $n-1$ 次二元分叉规则，共 $2n-1$ 次产生式应用。因为每个二元节点都把一段连续字符串分成两个非空部分，下一节的 CYK 才能枚举一个切分点，把问题拆成两个更短子串。

Greibach 标准形 GNF

GNF 的规则要求右侧第一个符号是终结符，后面只能是零个或多个变量：

\boxed{A\to aA_1\cdots A_k,\qquad k\ge0.}

同样可以为含空串的语言保留独立开始符号的空串例外。对非空字符串，每次最左推导恰好产生下一个终结符。因此一份长度为 $n$ 的成功最左推导恰用 $n$ 步。这不等于解析时没有选择：同一个变量可能有多条以同一字符开头的规则，需要额外条件才成为前一讲的 s-grammar。

转换的目标是消除规则开头的变量，并把首字符之后的终结符替换成代理变量。若右侧首变量没有递归依赖，直接代入它的全部规则即可。困难在于左递归：若 $A$ 能在尚未产生终结符时又回到最左侧的 $A$ ，简单代入会循环。

对直接左递归，把规则分为 $A\to A\alpha_i$ 和不以 $A$ 开头的 $A\to\beta_j$ 。在去掉空串和单位规则的条件下，每个 $\alpha_i$ 非空。用新变量 $B$ 改写为

\begin{aligned} A&\to\beta_j\mid\beta_jB \quad\text{（对每个 }j\text{）},\\ B&\to\alpha_i\mid\alpha_iB \quad\text{（对每个 }i\text{）}. \end{aligned}

原推导会先应用零次或多次左递归，再用某个 $\beta_j$ 结束，结果为 $\beta_j$ 后接有限多个 $\alpha$ 块；新变量 $B$ 恰好生成一个或多个这样的块， $A\to\beta_j$ 则处理零块。两种写法保留同一组结果。

一般转换从清理后的 CNF 的非空部分开始，给原变量编号 $A_1,\ldots,A_r$ 。独立开始符号的空串例外暂时放在一边保留。按以下顺序处理其余规则：

对 $i=1,\ldots,r$ 依次处理 $A_i$ 。在这一轮内部，再按 $j=1,\ldots,i-1$ 依次检查：凡当前 $A_i$ 规则以 $A_j$ 开头，就用 $A_j$ 的全部规则替换这个首变量。新产生的候选也进入本轮后续检查。处理完全部 $j$ 后，按上述公式消除 $A_i$ 的直接左递归，需要时建立新的辅助变量 $B_i$ 。
第一轮结束后，每个原变量的规则都以终结符或编号更大的原变量开头。现在按 $i=r,r-1,\ldots,1$ 倒序处理：凡 $A_i$ 的首符号是 $A_j$ ，必有 $j>i$ ，而 $A_j$ 此时已经全部以终结符开头。将它的规则代入， $A_i$ 也就全部以终结符开头。
最后处理新增的 $B_i$ 。从 CNF 出发，直接左递归尾部 $\alpha$ 的首符号仍是某个原变量；后加的辅助变量只位于这些尾部的后面。因此 $B_i\to\alpha\mid\alpha B_i$ 的首符号也为原变量。此时原变量已经全部处理完，代入其规则，就使 $B_i$ 也以终结符开头。后面的符号始终都是变量。恢复独立开始符号的空串例外后，转换完成。

第一轮为何能按编号向前推进？已处理的 $A_j$ 规则若以变量开头，只可能以编号大于 $j$ 的原变量开头。替换首部 $A_j$ 后，不会重新引入编号不大于 $j$ 的首变量；可能出现 $A_i$ 自身的情况，随后由直接左递归消除处理。这样，代入顺序确实能够走完，而不是反复回到原规则。

编号顺序使变量开头的依赖被逐步消除；直接左递归单独处理，使代入不会在自身上无止境循环。CNF 与 GNF 对任意 CFL 的非空部分都可构造，但 GNF 规则通常更难整理，转换不保证得到小文法。它们的价值是把语法树或推导步数变得便于统一分析。

CYK 的状态必须保存所有可能变量

CYK 的输入是 CNF 文法与字符串 $w=a_1\cdots a_n$ ，输出它是否属于该文法的语言。对 $1\le i\le j\le n$ ，定义

V[i,j]=\{A:A\Rightarrow^*a_i\cdots a_j\}.

也就是，表格单元保存能够生成这个连续子串的全部变量。它不是一个布尔值，也不能在找到第一个变量后停止，因为不同父规则可能需要不同变量。

长度为 1 的子串只能由终结符规则生成：

V[i,i]=\{A:A\to a_i\in P\}.

当 $i<j$ 时，任何生成该子串的树根必用某条 $A\to BC$ 。左孩子生成非空前半段，右孩子生成非空后半段，因此存在切分点 $k\in\{i,\ldots,j-1\}$ ：

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

                 A
              /     \
             B       C
             │       │
子串：   aᵢ ... aₖ | aₖ₊₁ ... aⱼ
           左半段      右半段

枚举切分位置，再检查是否有 A → BC 连接两边

CYK 的完整执行与正确性

CYK(G, w):
    若 w 为空：返回“开始符号是否能生成空串”的判断结果
    n = |w|
    对每个 i：V[i,i] = {A : A → w[i] 是规则}
    对长度 ℓ = 2, ..., n：
        对左端点 i = 1, ..., n-ℓ+1：
            j = i+ℓ-1
            V[i,j] = 空集
            对切分点 k = i, ..., j-1：
                对每条二元规则 A → BC：
                    若 B∈V[i,k] 且 C∈V[k+1,j]：
                        把 A 加入 V[i,j]
    当且仅当开始符号 S∈V[1,n] 时接受

按子串长度递增填表，所需的两部分都严格短于当前子串，因而必已计算。正确性也按长度归纳。

先证表中不会误加变量。边界中的每个变量都有对应终结符规则；较长子串中，若算法通过 $A\to BC$ 加入 $A$ ，归纳假设保证 $B,C$ 确实能分别生成两段，把两棵树接到 $A$ 下便生成当前子串。

再证不会遗漏变量。若 $A$ 确实生成长度大于 1 的子串，它的 CNF 树根必用 $A\to BC$ ，左右孩子必在某个合法位置分开。归纳假设保证 $B,C$ 会出现在相应较短单元格中，算法枚举到该切分点和规则时便加入 $A$ 。因此表中恰好是所有可生成变量，最终成员判定正确。

先填：长度 1 的全部子串
再填：长度 2 的全部子串
   ↓
最后：完整串 V[1,n]

每个长子串只读取已经完成的短子串

共有 $O(n^2)$ 个区间，每个枚举 $O(n)$ 个切分点，并检查文法的二元规则。用变量编号和布尔成员表实现集合查询，可得时间 $O(n^3|P|)$ ，空间 $O(n^2|V|)$ 。把文法视为固定输入之外的常量时，才简写为 $O(n^3)$ 时间、 $O(n^2)$ 空间。

若要输出语法树，在把 $A$ 加入 $V[i,j]$ 时记录一份成功依据：使用的规则 $A\to BC$ 和切分点 $k$ 。从 $(S,1,n)$ 开始递归取出左右记录，直到单字符规则，便恢复一棵语法树。只需一棵树时每个变量记录一个依据即可；若要枚举所有树，必须保存全部选择，结果数量也可能很大。

课件依据

讲次	原始资料	本篇覆盖的主要内容
Lec 1	数学基础与语言（本地课件），PDF 第 1–90 页	集合、函数、关系、图、证明、字符串、语言、文法
Lec 2	有限自动机（本地课件），第 1–207 页	DFA、NFA、空串闭包、等价转换、最小化
Lec 3	正则表达式（本地课件），第 1–104 页	表达式语义、双向转换、正则文法
Lec 4	正则语言性质（本地课件），第 1–103 页	封闭性、判定问题、泵引理、非正则证明
Lec 5	上下文无关文法（本地课件），第 1–90 页	CFG、语法树、歧义、解析与编译
Lec 6	文法变换与范式（本地课件），第 1–64 页	文法清理、CNF、GNF、CYK

来源链接用于核对课程范围；学习所需内容已在本文展开。文法与算法用一般符号说明，未另外加入练习或数值例题。

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