加权 ε 闭包与消边 | Codeboy's Blog

形式陈述

固定一个能保证收敛的模型

在加权有限自动机中，若每条边都读一个字符，固定字只有有限多条匹配路径。现在允许边标记为 $\varepsilon$ ，表示不消耗输入；一条 ε 自环就可能为同一个字提供无限多条有限运行。

本页固定有限状态集 $Q$ 、有限字母表与有限边多重集，初始权、终止权和全部边权都属于 $\mathbb Q_{\ge0}$ 。沿路径用普通乘法，路径之间用普通加法。初始权 $\lambda$ 是行向量，终止权 $\rho$ 是列向量；相同起终点、相同标签的平行边先相加。记 ε 边的矩阵为 $E$ ，字符 $a$ 的矩阵为 $M_a$ 。

一条匹配 $w$ 的有限路径，其非 ε 标签从左到右恰好拼成 $w$ ；贡献包含初始权、全部边权和终止权。定义 $A(w)$ 为这些非负贡献的总和，即所有有限路径子集的权重和的上确界，暂时允许为无穷。无限运行本身不作为一项加入。

用 $r(E)$ 表示谱半径，即 $E$ 在复数域中全部特征值的模的最大值，避免与终止向量 $\rho$ 混淆。若 $r(E)<1$ ，则矩阵级数收敛，且

\boxed{C=\sum_{k=0}^{\infty}E^k=(I-E)^{-1}.}

$C_{pq}$ 正是从 $p$ 到 $q$ 的全部有限 ε 路径权重和，包含长度零的路径。这里的 ε 路径权重只乘边权，不包含初始和终止权。虽然定义使用无限和， $C$ 的条目仍是非负有理数：非负性来自部分和，有理性来自有理可逆矩阵的逆。

每个字的矩阵式与消边构造

对 $w=a_1\cdots a_L$ ，有

\boxed{A(w)=\lambda C M_{a_1}C\cdots M_{a_L}C\rho.}

每两个相邻字符之间，以及首字符之前和末字符之后，都恰有一段 ε 路径。特别地，空字的值是 $\lambda C\rho$ ，通常不同于无 ε 边模型中的 $\lambda\rho$ 。

因此可在同一状态集上构造一台无 ε 边自动机：

\lambda'=\lambda C,\qquad M'_a=M_aC,\qquad \rho'=\rho.

每个正矩阵条目作为一条对应字符边，零条目不建边。先将初始 ε 段吸收进初始向量，再将每条字符边之后的 ε 段吸收进字符矩阵。新旧自动机对每个有限字权值相同，包括空字。等价的是路径贡献的总和，不是边数、路径条数或每条运行的一一对应。

直觉

普通ε-NFA只问某个状态能否到达，多条路径可以合并为一个“是”。加权模型还要保存每条解释的份额；反复绕环产生的新路径即使端点不变，也要继续贡献权值。

如果每次循环都足够衰减，无限多种选择的总贡献仍可以有限。闭包矩阵将这整族选择压缩为一次线性变换。随后读一个真实字符，再处理一段静默移动，就可以重复使用无 ε 边自动机的前向算法。

这种压缩不能随意重复。一个 ε 段若被前一字符的末尾闭包和后一字符的开头闭包同时分担，同一旧路径会对应多种切分，在普通数值加法下就被多次累计。

两状态加权自动机在p和q上分别以二分之一和三分之一循环，p到q的静默边权为四分之一，读取a后从q返回p — 每个成功的静默p到q段权重和为四分之三；每读一个a，就再需要一段这样的闭包

例子与边界

两个几何环，全部结果仍为有理数

状态顺序为 $(p,q)$ ，初始权 $\lambda=(1,0)$ ，终止权 $\rho=(0,1)^{\mathsf T}$ 。只有四条边：

起点	标签	终点	权重
$p$	$\varepsilon$	$p$	$1/2$
$p$	$\varepsilon$	$q$	$1/4$
$q$	$\varepsilon$	$q$	$1/3$
$q$	$a$	$p$	$1$

于是

E=\begin{pmatrix}1/2&1/4\\0&1/3\end{pmatrix}, \qquad M_a=\begin{pmatrix}0&0\\1&0\end{pmatrix}.

$E$ 的特征值为 $1/2,1/3$ ，所以满足条件。直接求逆得

C=\begin{pmatrix}2&3/4\\0&3/2\end{pmatrix}.

也可逐类路径验证：从 $p$ 回 $p$ 的纯 ε 路径只能在 $p$ 循环，总和为 $\sum_{j\ge0}(1/2)^j=2$ ；从 $q$ 回 $q$ 同理为 $3/2$ 。从 $p$ 到 $q$ 必须先在 $p$ 循环 $j$ 次，跨边一次，再在 $q$ 循环 $k$ 次，因此

C_{pq}=\sum_{j,k\ge0} (1/2)^j(1/4)(1/3)^k =2\cdot\frac14\cdot\frac32=\frac34.

没有从 $q$ 到 $p$ 的纯 ε 路径，所以 $C_{qp}=0$ 。消边得到

\lambda'=(2,3/4),\qquad M'_a=M_aC=\begin{pmatrix}0&0\\2&3/4\end{pmatrix}, \qquad \rho'=\rho.

新机器的前向向量为

(2,3/4)\xrightarrow{a}(3/2,9/16) \xrightarrow{a}(9/8,27/64).

终止向量只读取第二分量：

输入	矩阵求值	结果
$\varepsilon$	$\lambda C\rho$	$3/4$
$a$	$\lambda CM_aC\rho$	$9/16$
$aa$	$\lambda CM_aCM_aC\rho$	$27/64$

从原路径也能看出结果。每读一个 $a$ 必须从 $q$ 返回 $p$ ，最后又必须到 $q$ 终止。输入 $a^L$ 因而含 $L+1$ 段 $p\to q$ 的 ε 路径，中间的 $a$ 边权都是一。各段循环次数可独立选择，非负级数相乘给出

A(a^L)=(3/4)^{L+1}.

权重在这里没有被约定为概率；不需要各状态出边权加总为一，也不能根据例子小于一就自动添加概率解释。

前后都取闭包会怎样重复计数

若照搬布尔闭包的形式，错误地取 $B_a=CM_aC$ 并保留原初终向量，单个 $a$ 恰好正确，但两个 $a$ 之间出现了两个相邻的闭包：

\lambda B_aB_a\rho =\lambda CM_aC^2M_aC\rho.

本例

C^2=\begin{pmatrix}4&21/8\\0&9/4\end{pmatrix}\ne C, \qquad \lambda B_aB_a\rho =\frac34\cdot\frac{21}{8}\cdot\frac34 =\frac{189}{128}.

正确值只有 $27/64=54/128$ 。一般地，非负求和允许按总长度重排，

C^2=\sum_{i,j\ge0}E^{i+j} =\sum_{k\ge0}(k+1)E^k.

一条长 $k$ 的 ε 路径有 $k+1$ 个位置可以分成前后两段，重复正来自这些切点。布尔加法会消去重复的“真”；普通数值加法不会。这里还没有修复错误构造的空字值，单是 $aa$ 已足以否定它。

可逆、收敛与无关分量

一状态、初终权都为一、ε 自环权为一时，空字有总权 $\sum_{k\ge0}1=\infty$ 。若自环权改成二，总权仍发散，但 $I-E=-1$ 已经可逆，逆为 $-1$ 。因此仅检查矩阵可逆不够；负逆值也不可能表示非负路径的总和。

全局 $r(E)<1$ 是保证所有闭包条目有限的条件，却不是每个输入字的输出有限所必需。取

E=\operatorname{diag}(1/2,2),\quad M_a=\operatorname{diag}(1,0),\quad \lambda=(1,0),\quad\rho=(1,0)^{\mathsf T}.

第二状态根本不可从初始支持到达。所有成功路径留在第一状态，故 $A(a^L)=2^{L+1}$ 对每个有限 $L$ 都有限，尽管全局谱半径为二。

可以先按正权边与初终权支持删除不在任何成功路径上的状态，再分析剩余 ε 子图。不能先形成一个不存在的全局 $C$ ，再用“零乘无穷”解释 $\lambda C$ 。本页的消边定理明确要求用于构造的矩阵满足收敛条件。

推论与应用

谱半径为什么足以控制整个矩阵级数

在复数域中取Jordan 形 $E=PJP^{-1}$ 。一个大小为 $d$ 的块写成 $J_\mu=\mu I+N$ ，其中 $N^d=0$ 。若 $\mu=0$ ，该块本身幂零，级数只含前 $d$ 项；无需写含零的负幂的公式。

若 $0<|\mu|<1$ ，二项式展开给出

J_\mu^k =\sum_{j=0}^{\min(k,d-1)} \binom{k}{j}\mu^{k-j}N^j.

对固定 $j$ ，令 $r=|\mu|$ 。从 $k\ge\max(1,j)$ 开始，系数模至多为 $r^{-j}k^jr^k/j!$ 。序列 $k^jr^k$ 的相邻项比趋于 $r<1$ ，所以其级数收敛；前面的有限项单独保留。块中只有有限个 $j$ ，所以矩阵级数逐条目绝对收敛，且块的 $k$ 次幂趋零。

块数有限，再乘固定的 $P,P^{-1}$ ，同样得到 $\sum_kE^k$ 收敛及 $E^k\to0$ 。对有限部分和 $C_N=\sum_{k=0}^NE^k$ ，有

(I-E)C_N=C_N(I-E)=I-E^{N+1}.

取极限便证明 $C=(I-E)^{-1}$ 。反过来，整个矩阵级数若收敛，其项必须趋零；若存在特征值 $|\mu|\ge1$ 及非零特征向量 $v$ ，则 $E^kv=\mu^kv$ 不趋零，矛盾。因此对于整个有限维矩阵级数，这个谱条件也是必要的。

证明没有要求某个预先选定的矩阵范数小于一。例如 $E=\begin{pmatrix}0&10\\0&0\end{pmatrix}$ 的谱半径为零，而常用算子范数为十；它仍满足 $C=I+E$ 。有界长度的 ε 路径不需要每条边都衰减。

从有限截断到全部有限路径

首先按 ε 边条数归纳， $E^k(p,q)$ 恰是长度 $k$ 的 ε 路径边权乘积之和。 $k=0$ 给每个状态的一条零边路径；归纳步骤按最后一条边划分路径，用有限分配律得到矩阵乘法。

固定 $w=a_1\cdots a_L$ ，每条匹配路径都有唯一分解

\eta_0\,e_1\,\eta_1\,e_2\,\cdots\,e_L\,\eta_L,

$e_i$ 读 $a_i$ ， $\eta_i$ 是零条或多条 ε 边。切点就是实际读取字符的位置，与经过多少次相同状态无关。

令 $\mathcal P_N(w)$ 只保留每段 $\eta_i$ 长度不超过 $N$ 的路径。它是有限集，直接展开矩阵乘积即得

\sum_{\pi\in\mathcal P_N(w)}\mathrm{wt}(\pi) =\lambda C_NM_{a_1}C_N\cdots M_{a_L}C_N\rho.

这些路径集递增，且穷尽所有有限匹配路径。更强地，任意有限路径子集都有一个共同的最大 ε 段长度，因此被某个 $\mathcal P_N(w)$ 包含。由非负路径和的上确界定义，左侧极限就是 $A(w)$ ；由有限矩阵乘法对条目极限的连续性，右侧极限就是声明中的闭包公式，同时说明结果有限。

代入 $\lambda',M'_a,\rho'$ ，无 ε 边机器的矩阵式逐项恢复该公式。 $L=0$ 时也是 $\lambda'\rho'=\lambda C\rho$ ，因而空字没有被遗漏。另一种一致的吸收方向是保留 $\lambda'=\lambda$ 、取 $M'_a=CM_a$ 和 $\rho'=C\rho$ ；两种方向都把每一段 ε 路径恰好归入一次。

执行与适用范围

可以用有理数线性代数求解 $(I-E)C=I$ ，再形成初始向量和字符矩阵。稠密消元及每个矩阵乘法通常需 $O(|Q|^3)$ 次算术操作；转移可能变稠密，之后长 $L$ 的字可用 $O(|Q|+L|Q|^2)$ 次算术操作求值。分子、分母的位长还会影响实际成本，这不是固定字长时间保证。

收敛前提应在求逆之外单独证明。对于这里的有理矩阵，Jordan 论证提供数学判据，小例可精确求特征值；实际数值计算若仅看到浮点近似“略小于一”，并没有自动获得严格证书。

这类消边适合把静默选择与实际字符处理分离，但不直接覆盖带负权相消、热带运算或任意半环。特别地，非负有理数并不天然对任意无限和封闭。本页通过谱条件和截断证明建立所需闭包，没有把一般加权消边文献中的完备半环假设默认为已经成立。

终点自测：独立计算两态例子的 $C$ 、 $M'_a$ 与三个输入值，再把错误双闭包算成 $189/128$ ；最后解释自环权二时逆矩阵虽存在却不能解释路径和，以及不可达发散分量为何不影响给定输出。

参考资料

Mehryar Mohri, Weighted Automata Algorithms, in Handbook of Weighted Automata, 2009，§6.1，pp. 21–25，式 (28)–(29)、Theorem 4 及反向消边：ε 路径权汇总、吸收方向和最终权修正。该定理以完备半环及可计算闭包为前提；本页有理权谱条件的收敛与消边由上面的独立证明给出。
James V. Burke, University of Washington, Math 554: Linear Analysis, Autumn 2004, Lecture Notes，Chapter 5，§1.1，印刷 pp. 64–65：谱半径与 Neumann 级数、指定算子范数可能大于一的边界及 Proposition 1.2。本文展开有限维 Jordan 块证明，并单独处理零特征值块。

形式陈述 ​

固定一个能保证收敛的模型 ​

每个字的矩阵式与消边构造 ​

两个几何环，全部结果仍为有理数 ​

前后都取闭包会怎样重复计数 ​

可逆、收敛与无关分量 ​

谱半径为什么足以控制整个矩阵级数 ​

从有限截断到全部有限路径 ​

执行与适用范围 ​

反向链接