词理论基础

· · 算法·理论

词理论基础

1.1 自由幺半群与词

定义 1.1.1 (字母表, 词)

任给非空集 A 称为 字母表 (alphabet)，称 a \in A 为一个 字母 (letter)，而称 A 中元素组成的 有限长 序列为以 A 为字母表的 词 (word)，则这些词构成集合

A^* = \bigsqcup_{n \in \mathbb{N}} A^n

则有自然的词拼接运算

\begin{aligned} \cdot : A^* \times A^* &\to A^* \\ ([a_1, \cdots, a_n], [b_1, \cdots, b_m]) &\mapsto [a_1, \cdots, a_n, b_1, \cdots, b_m] \end{aligned}

容易验证 \cdot 满足结合律。此处 \cdot 常省略，而 [a_1, \cdots, a_n] 常略作 a_1 \cdots a_n。

记 \varepsilon 为空词 [] \in A^0，则 (A^*, \cdot, \varepsilon) 构成 幺半群。

命题 1.1.2 (词的泛性质)

设 A 非空，则 A^* 为 A 上的 自由幺半群，也即任给幺半群 M 和映射 \alpha : A \to M，存在唯一的同态 \varphi : A^* \to M，使得 \alpha = \varphi \circ i，其中 i : A \hookrightarrow A^* 为自然嵌入 a \mapsto [a]。

Proof. 由同态的性质可知 \varphi 必然满足

\varphi(a_1 \cdots a_n) = \alpha(a_1) \cdots \alpha(a_n), \quad n \in \mathbb{N}, a_i \in A

这就唯一地确定了 \varphi，同时其亦是良定义且满足条件的。明所欲证。

定义 1.1.3

定义长度映射

\begin{aligned} | \cdot | : A^* &\to \mathbb{N} \\ w &\mapsto n, &\quad w \in A^n \end{aligned}

则易见 | \cdot | 为从 A^* 到 (\mathbb{N}, +, 0) 的同态。

记 |w|_a \ (w \in A^*, a \in A) 表示 w 中 a 的出现次数，即由映射

a \mapsto 1, \quad b \mapsto 0 \ (b \in A \backslash \{a\})

诱导的同态，则有

|w| = \sum_{a \in A} |w|_a

容易见得求和中只有有限多项非零，故其是良定义的。

记 \text{alph}(w) 为 w 中实际出现的字母集，即

\text{alph}(w) = \{a \in A \mid |w|_a > 0\}

则易见 \text{alph} 为从 A^* 到 (\mathcal{P}(A), \cup, \varnothing) 的同态。

定义 1.1.4 (子词, 真子词, 前缀, 真前缀, 可比)

称 v \in A^* 为 x \in A^* 的 子词 (factor)，若

\exists u, w \in A^*, \text{s.t. } x = uvw

特别地，称 v 为 x 的 真子词 (proper factor)，若还满足 v \neq x。

称 v 为 x 的 前缀 (left factor / prefix)，若

\exists w \in A^*, \text{s.t. } x = vw

特别地，称 v 为 x 的 真前缀 (proper left factor / proper prefix)，若还满足 v \neq x。

同理还可以定义后缀和真后缀。容易验证子词、前缀、后缀关系各自构成 A^* 上的一个偏序。

称 v, v' \in A^*（在前缀关系下）可比 (comparable)，若 v 为 v' 的前缀或 v' 为 v 的前缀。同理可以定义在后缀关系下可比。

命题 1.1.5 (等可分性 / equidivisibility)

设 x, v, v' \in A^*，若 v, v' 均为 x 的前缀，则 v, v' 可比。

Proof. 设 x = vw = v' w'，对 |v| 归纳：

综上明所欲证。

定义 1.1.6 (反转, 回文)

设 w = a_1 \cdots a_n \in A^* \ (n \in \mathbb{N}, a_i \in A)，定义其 反转 (reversal) 为 \tilde{w} = a_n \cdots a_1。

称 w 回文 (palindrome)，若 \tilde{w} = w。

易见以下性质：

定义 1.1.7 (子序列)

称 v = a_1 \cdots a_n \in A^* \ (n \in \mathbb{N}, a_i \in A) 为 w \in A^* 的 子序列 (subword)，若存在一列 y_0, \cdots, y_n \in A^*，使得

w = y_0 a_1 y_1 \cdots a_n y_n

容易发现子词蕴含子序列。

定义 1.1.8 (边界)

称 v \in A^* 为 w \in A^* 的 边界 (border)，若 v 同时为 w 的前缀和后缀。

1.2 子幺半群与态射

定义 1.2.1 (生成幺半群, 最小生成集)

给定 X \subset A^*，定义 X^* 为 X 经词拼接操作有限生成的幺半群：

X^* \triangleq \{x_1 \cdots x_n \mid n \in \mathbb{N}, x_i \in X\}

方便起见，对 x \in A^* 记 x^* \triangleq \{x\}^*。

相反地，任给 A^* 的子幺半群 P，称 X \subset A^* 为其 最小生成集 (minimal generating set)，若 X^* = P 且 X 在子集关系下最小。

容易验证 X 总是存在，其为 (P \backslash \{\varepsilon\}) \backslash (P \backslash \{\varepsilon\})^2，且满足 \varepsilon \not\in X。

命题 1.2.2 (子幺半群自由的充要条件)

设 P 为 A^* 的子幺半群，X 为 P 的最小生成集，则 P 为 X 上的自由幺半群当且仅当 X 给出 P 中元素的唯一分解，即

\forall n, m \in \mathbb{N}, x_i, y_j \in X, (x_1 \cdots x_n = y_1 \cdots y_m \Rightarrow n = m, x_i = y_i)

Rmk. 方便起见，后面将“P 为 X 上的自由幺半群”略作“P 为自由幺半群”。

Proof. 下记自然嵌入 i_X : X \hookrightarrow P。

先证充分性。任给幺半群 M 和同态 f : X \to M，欲证存在唯一的同态 \varphi : P \to M，使得 f = \varphi \circ i_X。

先证唯一性。由同态的性质可见 \varphi 必然满足

\varphi(\varepsilon) = 1_M, \quad \varphi(x_1 \cdots x_n) = f(x_1) \cdots f(x_n)

这就唯一确定了 \varphi。

再证存在性。唯一分解性说明上面给出的 \varphi 良定义，还需说明 \varphi 确为同态。

只需验证其保持运算：设 u = x_1 \cdots x_n, v = y_1 \cdots y_m \ (n, m \in \mathbb{N}, x_i, y_j \in X)，则有

\begin{aligned} \varphi(uv) &= \varphi(x_1 \cdots x_n y_1 \cdots y_m) \\ &= f(x_1) \cdots f(x_n) f(y_1) \cdots f(y_m) \\ &= (f(x_1) \cdots f(x_n)) (f(y_1) \cdots f(y_m)) \\ &= \varphi(u) \varphi(v) \end{aligned}

故 P 为 X 上的自由幺半群，明所欲证。

再证必要性。设 P 为自由幺半群，考察双射 \beta : X \to B，记自然嵌入 i_B : B \hookrightarrow B^*，则 i_B \circ \beta : X \to B^* 诱导出同态 \varphi : P \to B^*。

若 w = x_1 \cdots x_n = y_1 \cdots y_m \in P，则 \varphi(w) = \beta(x_1) \cdots \beta(x_n) = \beta(y_1) \cdots \beta(y_m)，由 \text{im } \beta = B 可见二者均为 \varphi(w) 作为 B-词的唯一分解，故 n = m, x_i = y_i。

定义 1.2.3 (码, 前缀集)

称 A^* 的自由子幺半群 P 的最小生成集为 码 (code)，又称 基 (basis)。

称 X \subset A^* 为前缀集，若

\forall x, y \in X, x, y \text{ 可比} \Rightarrow x = y

例子 1.2.4

令 A = \{a, b\}，则：

命题 1.2.5

设 X \subset A^* 为前缀集，若 \varepsilon \not\in X，则 X 是码。

Proof. 由 命题 1.2.2 只需验证唯一分解性，当分解非空时由 命题 1.1.5 可知两个首项可比，前缀集的定义迫使二者一致，进而消去后据归纳假设即证。

命题 1.2.6

$$ \forall w \in A^*, (\exists p, q \in P, \text{s.t. } pw, wq \in P) \Rightarrow w \in P $$

Proof. 设 X 为 P 的最小生成集。

先证必要性。考察双射 \beta : B \to X，由 命题 1.2.2 诱导出自由幺半群的同构 \beta : B^* \to P，设 \beta(a) = p, \beta(b) = q, \beta(c) = pw, \beta(d) = wq \ (a, b, c, d \in B^*)，则 \beta(ad) = \beta(cb) = pwq。

由同构可见 ad = cb，由 命题 1.1.5 不妨设 a 为 c 的前缀，则 \exists t \in B^*, \text{s.t. } c = at，于是 pw = \beta(at) = p \beta(t)，消去 p 得到 \beta(t) = w，故 w \in P。

再证充分性。设 n, m \in \mathbb{N}, x_i, y_j \in X，当 x_1 \cdots x_n = y_1 \cdots y_m，对 n 归纳：

推论 1.2.7

Proof. 设 (P_i)_{i \in I} 为 A^* 的一族自由子幺半群，首先 P = \displaystyle\bigcap_{i \in I} P_i 仍为子幺半群，其次根据 命题 1.2.6 任给 w \in A^*，若

\exists p, q \in P \subset P_i, \text{s.t. } pw, wq \in P \subset P_i

则对每个 i 施用 命题 1.2.6 得到 w \in P_i，故 w \in P。

定义 1.2.8 (自由包)

设 X \subset A^*，记 \mathcal{F} = \{A^* \text{ 的自由子幺半群 } P \mid X \subset P\} 为 A^* 的一族自由子幺半群，令

S = \bigcap_{P \in \mathcal{F}} P

则由 推论 1.2.7 可知其仍自由，故其为子集关系下最小的自由子幺半群，其最小生成集（码）Y 称为 X 的 自由包 (free hull)。

定理 1.2.9 (缺陷定理 / defect theorem)

有限集 X \subset A^* 若不是码，则其自由包 Y 满足 |Y| \leq |X| - 1。

Proof. 当 \varepsilon \in X，可见其自由包与 X \backslash \{\varepsilon\} 一致；下面讨论 \varepsilon \not\in X 的情形，定义映射

\begin{aligned} \alpha : X &\to Y \\ x &\mapsto y, &\quad x \in yY^* \end{aligned}

由 Y 为码可见 \alpha 良定义。

一方面，由 X 不为码可取 n + m 最小的二义分解

x_1 \cdots x_n = y_1 \cdots y_m, \quad n, m \in \mathbb{N}_+, x_i, y_j \in X, x_1 \neq y_1

设 x_i = \alpha(x_i) u_i, y_j = \alpha(y_j) v_j \ (u_i, v_j \in Y^*)，则有：

\alpha(x_1) u_1 \cdots \alpha(x_n) u_n = \alpha(y_1) v_1 \cdots \alpha(y_m) v_m

由 Y 为码即得 \alpha(x_1) = \alpha(y_1)，故 \alpha 不单。

另一方面，若 \alpha 不满，设 z \in Y 但 z \not\in \alpha(X)，记 Z = (Y \backslash \{z\}) z^*。

先证 Z 为码。设 \tilde{x}_1 \cdots \tilde{x}_n = \tilde{y}_1 \cdots \tilde{y}_m \ (n, m \in \mathbb{N}, \tilde{x}_i, \tilde{y}_j \in Z)，则有 Y^* 中的等式

x_1 z^{p_1} \cdots x_n z^{p_n} = y_1 z^{q_1} \cdots y_m z^{q_m}, \quad \tilde{x}_i = x_i z^{p_i}, \tilde{y}_j = y_j z^{q_j}, x_i, y_j \in Y \backslash \{z\}, p_i, q_j \in \mathbb{N}

由 Y 为码可知 n = m, x_i = y_i, p_i = q_i 即 \tilde{x}_i = \tilde{y}_i，由 命题 1.2.2 即得 Z 也为码。

再证 X \subset Z^*。任给 x = x_1 \cdots x_n \in X \ (n \in \mathbb{N}, x_i \in Y)，由 \alpha(x) \neq z 可知 x_1 \neq z，故总能写作

x = y_1 z^{p_1} \cdots y_m z^{p_m}, \quad m \in \mathbb{N}, y_i \in Y \backslash \{z\}, p_i \in \mathbb{N}

的形式，故 x \in Z^*，因而 X \subset Z^*。

最后证 Z^* \subsetneq Y^*。任给 w = \tilde{x}_1 \cdots \tilde{x}_n \in Z^* \ (n \in \mathbb{N}, \tilde{x}_i \in Z)，设 \tilde{x}_i = x_i z^{p_i} \ (x_i \in Y, p_i \in \mathbb{N})，则

w = x_1 z^{p_1} \cdots x_n z^{p_n} \in Y^*

故 Z^* \subset Y^*；一方面 z \in Y^*，另一方面若 z \in Z^* 则

z = x_1 z^{p_1} \cdots x_n z^{p_n}, \quad n \in \mathbb{N}, x_i \in Y \backslash \{z\}, p_i \in \mathbb{N}

由 z \neq x_1 推出矛盾！故 z \not\in Z^*，因而 Z^* \subsetneq Y^*。

总之 Z^* 是比 Y^* 更小且包含 X 的自由子幺半群，与 Y^* 的最小性矛盾！故 \alpha 满。

综上，\alpha 满而不单，故 |Y| \leq |X| - 1。

推论 1.2.10

设 x, y \in A^*，若不存在词 z \in A^* 使得 x, y \in z^*，则 \{x, y\} 为码。

Proof. 假设 \{x, y\} 不是码，则由 定理 1.2.9 可知其自由包 H 满足 |H| \leq 1，分类讨论：

总之明所欲证。

定义 1.2.11 (非抹除)

称同态 \varphi : B^* \to A^* 非抹除 (nonerasing)，若 \varphi(B^+) \subset A^+，此时容易归纳证明

\forall w \in B^*, |\varphi(w)| \geq |w|

1.3 共轭

定义 1.3.1 (本原)

称词 x \in A^* 本原 (primitive)，若 x \neq \varepsilon 且 \forall z \in A^*, x \in z^* \Rightarrow x = z。

定义 & 命题 1.3.2 (本原根, 指数)

(1) 设 x, y \in A^*，若 x^n = y^m \ (n, m \in \mathbb{N}_+)，则 \exists z \in A^*, \text{s.t. } x, y \in z^*。\ (2) 设 w \in A^+，则存在唯一的本原词 x \in A^+，使得 w \in x^*，此时称 x 为 w 的本原根，令 w 的指数为 \dfrac{|w|}{|x|} \in \mathbb{N}_+。

Proof. (1) 分类讨论：

综上明所欲证。

(2) 记 S = \{x \in A^+ \mid w \in x^*\}，由 w \in S 可见 S 非空，故可取其中长度最小的词（之一）为 x \in A^+。

若 x 不本原，设还有 z \in A^* 使得 x \in z^* 但 x \neq z，则 w \in z^* 且 0 < |z| < |x|，于是 z \in S，与 x 长度最小矛盾！

若 x' \in A^+ 也为 S 中长度最小的词，则由 (1) 可知 \exists p \in A^*, \text{s.t. } x, x' \in p^*，进而 p \neq \varepsilon, |p| \mid |x| 且 x = x' = p^{\frac{|x|}{|p|}}，故 x 唯一。

总之 x 为唯一满足条件的本原词，明所欲证。

命题 1.3.3

(1) x, y \in A^+ 可交换（即 xy = yx）当且仅当其为同一非空词的幂。\ (2) 所有与 x \in A^+ 可交换的词构成由单个本原词生成的幺半群。

Proof. (1) 充分性是显然的；而由 xy = yx 可见 \{x, y\} 不是码，由 推论 1.2.10 即得必要性。

(2) 设 z 为 x 的本原根，当 y \in A^+ 与 x 可交换则由 (1) 可见 \exists t \in A^+, \text{s.t. } x, y \in t^*。

由 命题 1.3.2 可知 \exists s \in A^*, \text{s.t. } z, t \in s^*，由 z 本原可见 s = z, t \in z^*，进而 y \in z^*。

反之只要 y \in z^* 就有 x, y 交换，故与 x 构成的词构成幺半群 z^*。明所欲证。

定义 1.3.4 (共轭)

称 x, y \in A^* 共轭，若 \exists u, v \in A^*, \text{s.t. } x = uv, y = vu。

由 命题 1.1.5 容易验证共轭构成 A^* 上的一个等价关系：事实上共轭无非是说可以通过循环移位互相转化。

命题 1.3.5

(1) 设 x, y \in A^+ 长度相同，z, t \in A^+ 分别为二者的本原根，则 x, y 共轭当且仅当 z, t 共轭，此时 x, y 指数相同。\ (2) 设 z, t \in A^+ 为共轭的本原词，则 \exists ! (u, v) \in A^* \times A^+, \text{s.t. } z = uv, t = vu。\ (3) 设 z \in A^+ 本原，则 z 所在共轭类中恰有 |z| 个词，且均本原。

Proof. (1) 设 z 为 x 的本原根，k 为 x 的指数。

先证必要性。设 x = rs, y = sr，则 \exists u, v \in A^*, k_1 + k_2 + 1 = k, \text{s.t. } z = uv, r = z^{k_1} u, s = vz^{k_2}，进而 y = (vu)^k \triangleq t^k，显见 z, t = vu 共轭。

再证充分性。设 $z = uv, t = vu$，则由长度相同可见 $x, y$ 的指数均为 $k$，且 $x = (uv)^k = u ((vu)^{k - 1} v), y = (vu)^k = ((vu)^{k - 1} v) u$，故 $x, y$ 共轭。 (2) 先证存在性。由共轭的定义可知 $\exists u, v \in A^*, \text{s.t. } z = uv, t = vu$，当 $v \neq \varepsilon$ 时 $(u, v)$ 即为所求，否则有 $z = t = u \neq \varepsilon$、故 $(\varepsilon, u)$ 为所求。 再证唯一性。设 $(u', v') \in A^* \times A^+$ 也满足条件，则 $uv = u' v', vu = v' u'$，不妨设 $u$ 为 $u'$ 的前缀，由 **命题 1.1.5** 可知 $\exists r \in A^*, \text{s.t. } u' = ur$，则 $v = rv'$，故 $r(v' u) = (v' u)r$。 当 $r = \varepsilon$ 可见 $(u', v') = (u, v)$；否则由 **命题 1.3.3** 可见 $\exists s \in A^+, p, q \in \mathbb{N}_+, \text{s.t. } r = s^p, v' u = s^q$，故 $t = v' u' = s^{p + q}$，与 $t$ 本原矛盾！明所欲证。 (3) 同 $(*)$ 可知 $z$ 所在共轭类 $C_z$ 中的词均本原。令 $S = \{v \in A^+ \mid \exists u \in A^*, \text{s.t. } z = uv\}$，则由 (2) 可见 $$ \begin{aligned} S &\to C_z \\ v &\mapsto vu, &\quad z = uv \end{aligned} $$ 良定义且为双射。故 $|C_z| = |S| = |z|$，明所欲证。 #### 命题 1.3.6 > (1) $x, y \in A^+$ 共轭当且仅当 $\exists z \in A^*, \text{s.t. } xz = zy$。\ > (2) 设 $x, y \in A^+, z \in A^*$，则 $xz = zy$ 当且仅当 $\exists u, v \in A^*, \text{s.t. } x = uv, y = vu, z \in u(vu)^*$。 _Proof._ (1) 先证必要性。设 $x = uv, y = vu$，则令 $z = u$ 即可。 再证充分性。归纳可见对 $n \in \mathbb{N}_+$ 皆有 $x^n z = zy^n$，取 $n$ 使得 $(n - 1) |x| \leq |z| \leq n |x|$，设 $z = x^{n - 1} u, x = uv, vz = y^n$。 于是 $y^n = (vu)^n$，则 $y = vu$，故 $x, y$ 共轭。 (2) 充分性显然，而必要性由 (1) 立即可得：因为必有 $z = u(vu)^{n - 1} \in u(vu)^*$。 #### 注记 1.3.7 当 $k = |A|$ 有限，即 $\psi_k(n)$ 为 $A$ 上长为 $n$ 的本原词共轭类的数量。若 $|w| = n$，记 $z$ 为 $w$ 之本原根，且 $d = |z|, qd = n$，则由 **命题 1.3.5 (3)** 可知 $$ k^n = \sum_{d \mid n} d \psi_k(d) $$ 由 Möbius 反演可知 $$ \psi_k(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) k^{\frac{n}{d}} $$ #### 定理 1.3.8 (Fine & Wilf, 前缀表述) > 设 $x, y \in A^+$，$n = |x|, m = |y|, d = \gcd(n, m)$，若 $x^p, y^q$ 有一个长度至少为 $n + m - d$ 的公共前缀，则 $x, y$ 为同一个词的幂。 _Proof._ 当 $n = d$ 或 $m = d$，不妨设为前者，则 $x^p, y^q$ 有长为 $m$ 的公共前缀，则 $y = x^{\frac{m}{n}}$，故 $x, y$ 为 $x$ 的幂。 下面考虑 $d < n, m$ 的情形。设 $u$ 为 $x^p, y^q$ 的长为 $n + m - d$ 的公共前缀，由 $u$ 为 $x^p, y^q$ 之前缀可见 $u$ 同时有周期 $n, m$： $$ \begin{cases} \forall 1 \leq i \leq m - d, u_i = u_{i + n} \\ \forall 1 \leq j \leq n - d, u_j = u_{j + m} \end{cases} $$ 显见 $n \leq m - d, m \leq n - d$ 之中至少有其一成立，不妨设为前者。 若 $1 \leq i, j \leq m - d, j = (i + n - 1) \bmod m + 1$，则： - 要么 $j = i + n$，这意味着 $u[j] = u[i]$； - 要么 $j = (i + n) - m$，这意味着 $u[j] = u[i + n] = u[i]$。 总之 $u[j] = u[i]$。考虑字母表 $B = A^d$，将 $x, y, u$ 视为 $B^*$ 中的词 $x', y', u'$ 并令 $n' = \dfrac{n}{d}, m' = \dfrac{m}{d}$，则 $n' \leq m' - 1$，并有 $$ \forall 1 \leq i, j < m', j = (i + n' - 1) \bmod m' + 1 \Rightarrow u'[j] = u'[i] $$ 由 $n' \perp m'$ 可知 $\{1, \cdots, m'\}$ 通过 $+ n'$ 在 $\bmod m'$ 意义下构成 **单循环**，删掉 $m'$ 这一点后为一条连通路径，故 $\forall 1 \leq i, j < m', u'[i] = u'[j]$。 因此各 $u'[i] \ (1 \leq i < m')$ 相等，而由 $n' \leq m' - 1$ 及周期性可见 $u'[m'] = u'[m' - n']$，于是各 $u'[i] \ (1 \leq i \leq m')$ 皆相等。 令 $z = u'[1] \in B = A^d \subset A^*$，则 $x = z^{n'}, y = z^{m'}$，明所欲证。 #### 注记 1.3.9 可以举例说明 **定理 1.3.8** 给出的界是紧的。定义 Fibonacci 数列： $$ F_1 = F_2 = 1, \quad F_{n + 1} = F_n + F_{n - 1} \ (n \geq 2) $$ 则 $F_n \perp F_{n + 1}$。考虑 $A = \{a, b\}$ 上的 Fibonacci 词： $$ f_1 = b, f_2 = a, \quad f_{n + 1} = f_n f_{n - 1} \ (n \geq 2) $$ 当 $n \geq 3$，记 $g_n$ 为 $f_n$ 的长为 $F_n - 2$ 的前缀。则当 $n \geq 6$ 有 $g_{n + 1} = f_n g_{n - 1}$，进而 $$ g_{n + 1} = f_n f_{n - 2} g_{n - 3} = f_{n - 1} f_{n - 2} f_{n - 3} f_{n - 4} g_{n - 3} = f_{n - 1}^2 g_{n - 2} $$ 故此时 $f_{n + 1}$ 为 $f_n^2$ 的前缀，$g_{n + 1}$ 为 $f_{n - 1}^3$ 的前缀，则 $f_n^2, f_{n - 1}^3$ 有长为 $F_{n + 1} - 2$ 的公共前缀，但 $f_n, f_{n - 1}$ 并非同一词的幂。 例如当 $n = 6$ 有： $$ \begin{cases} f_6^2 = \textbf{abaababaaba} ababa \\ f_5^3 = \textbf{abaababaaba} baab \\ \end{cases} $$ 可见二者恰有长为 $F_7 - 2 = 11$ 的公共前缀。 ### 1.4 形式级数 词的计数常常通过从自由幺半群到环的映射实现，这启发我们引入形式级数。 #### 定义 1.4.1 (形式级数, 多项式) 设 $K$ 为交换幺环，称从自由幺半群 $A^*$ 到 $K$ 的映射为系数在 $K$ 中、变元在 $A$ 上的 **形式级数 (formal series)**，记作 $K \langle \langle A \rangle \rangle = K^{A^*}$。 设 $\sigma \in K \langle \langle A \rangle \rangle, w \in A^*$，$\sigma$ 在 $w$ 处的取值记作 $\langle \sigma, w \rangle \in K$，称为 $\sigma$ 在 $w$ 处的系数。 任给 $X \subset A^*$，记 $\underline{X}$ 为 $X$ 的 **特征级数 (characteristic series)**，定义为 $$ \langle \underline{X}, x \rangle = [x \in X] $$ 简洁起见，令 $\underline{x} \triangleq \underline{\{x\}}, 0 \triangleq \underline{\varnothing}, 1 \triangleq \underline{\varepsilon}$。 定义 $K \langle \langle A \rangle \rangle$ 上的加法和乘法如下： $$ \begin{aligned} \langle \sigma + \tau, w \rangle &= \langle \sigma, w \rangle + \langle \tau, w \rangle \\ \langle \sigma \tau, w \rangle &= \sum_{w = uv} \langle \sigma, u \rangle \langle \tau, v \rangle \end{aligned} $$ 则 $(K \langle \langle A \rangle \rangle, +, \cdot, 0, 1)$ 构成含幺结合代数。 当 $\sigma \in K \langle \langle A \rangle \rangle$ 只有有限个系数非零，称为 **多项式 (polynomial)**，其构成的集合 $K \langle A \rangle$ 称为 $A$ 上的 **自由结合 $K$-代数**。 任给 $\sigma \in K \langle \langle A \rangle \rangle, \tau \in K \langle A \rangle$，定义 $$ \langle \sigma, \tau \rangle = \sum_{w \in A^*} \langle \sigma, w \rangle \langle \tau, w \rangle $$ ……其中只有有限个 $w$ 使得 $\langle \tau, w \rangle$ 非零，故求和是良定义的。易见这是一个双线性映射。 #### 定义 1.4.2 (局部有限) 称一族形式级数 $(\sigma_i)_{i \in I}$ **局部有限 (locally finite)**，若 $\forall w \in A^*$，只有有限个 $i \in I$ 对应的系数 $\langle \sigma_i, w \rangle$ 非零。 当 $(\sigma_i)_{i \in I}$ 局部有限，求和 $$ \sigma = \sum_{i \in I} \sigma_i $$ 良定义，这是因为任给 $w \in A^*$，$\langle \sigma, w \rangle$ 都是有限个非零系数 $\langle \sigma_i, w \rangle$ 之和。 特别地，$(\underline{w})_{w \in A^*}$ 局部有限，故任给 $\sigma \in K \langle \langle A \rangle \rangle$ 皆成立等式 $$ \sigma = \sum_{w \in A^*} \langle \sigma, w \rangle \underline{w} $$ 事实上，这正是单变量形式幂级数记号的拓展： $$ \sigma = \sum_{n \in \mathbb{N}} \sigma_n a^n, \quad \sigma_n = \langle \sigma, a^n \rangle $$ #### 定义 1.4.3 (星) 设 $\sigma \in K \langle \langle A \rangle \rangle$ 满足 $\langle \sigma, \varepsilon \rangle = 0$，则 $(\sigma^i)_{i \in \mathbb{N}}$ 局部有限：这是因为 $\forall i > |w|, \langle \sigma^i, w \rangle = 0$。 于是可以定义形式级数 $$ \sigma^* = \sum_{i \in \mathbb{N}} \sigma^i $$ 称为 $\sigma$ 的 **星 (star)**。 #### 命题 1.4.4 > 设 $\sigma \in K \langle \langle A \rangle \rangle$ 满足 $\langle \sigma, \varepsilon \rangle = 0$，则 $\sigma^*$ 是唯一使得 > $$ > \sigma^* (1 - \sigma) = (1 - \sigma) \sigma^* = 1 > $$ > 成立的形式级数。 _Proof._ 先证上式成立。两式对称，只需证明前者。任给 $w \in A^*$，有 $$ \begin{aligned} & \langle \sigma^* (1 - \sigma), w \rangle \\ = \ & \sum_{w = uv} \langle \sigma^*, u \rangle \langle 1 - \sigma, v \rangle \\ = \ & \sum_{w = uv} \left( \sum_{i \in \mathbb{N}} \langle \sigma^i, u \rangle \right) ([v = \varepsilon] - \langle \sigma, v \rangle) \\ = \ & \sum_{i \leq |w|} \langle \sigma^i, w \rangle - \sum_{w = uv} \left( \sum_{i \leq |w|} \langle \sigma^i, u \rangle \right) \langle \sigma, v \rangle &\quad (\text{有限化}) \\ = \ & \left\langle \sum_{i \leq |w|} \sigma^i, w \right\rangle - \sum_{w = uv} \left\langle \sum_{i \leq |w|} \sigma^i, u \right\rangle \langle \sigma, v \rangle &\quad (\text{加法合并}) \\ = \ & \left\langle \sum_{i \leq |w|} \sigma^i, w \right\rangle - \left\langle \left( \sum_{i \leq |w|} \sigma^i \right) \sigma, w \right\rangle &\quad (\text{乘法合并}) \\ = \ & \langle 1 - \sigma^{|w| + 1}, w \rangle \\ = \ & [w = \varepsilon] \end{aligned} $$ 由外延性即得 $\sigma^* (1 - \sigma) = 1$。 再证满足条件的 $\tau \in K \langle \langle A \rangle \rangle$ 唯一。依 $|w|$ 归纳： - (i) 当 $|w| = 0$ 即 $w = \varepsilon$，要求 $\langle \tau (1 - \sigma), \varepsilon \rangle = \langle \tau, \varepsilon \rangle (1 - \langle \sigma, \varepsilon \rangle) = \langle \tau, \varepsilon \rangle = 1$，故 $\langle \tau, \varepsilon \rangle$ 只能为 $1$。 - (ii) 当 $|w| > 0$，要求 $\langle \tau (1 - \sigma), w \rangle = 0$，而 $$ \begin{aligned} & \langle \tau (1 - \sigma), w \rangle \\ = \ & \sum_{w = uv} \langle \tau, u \rangle \langle 1 - \sigma, v \rangle \\ = \ & \langle \tau, w \rangle - \sum_{w = uv, v \neq \varepsilon} \langle \tau, u \rangle \langle \sigma, v \rangle \end{aligned} $$ - 这就迫使 $\langle \tau, w \rangle = \displaystyle\sum_{w = uv, v \neq \varepsilon} \langle \tau, u \rangle \langle \sigma, v \rangle$，而和式各项对应的 $|u| < |w|$，故由归纳假设可知 $\langle \tau, w \rangle$ 唯一。 综上明所欲证。 #### 命题 1.4.5 > 设 $X, Y \subset A^*$，$\text{char } K = 0$，则： > > (1) 设 $Z = X \cup Y$，则 $\underline{Z} = \underline{X} + \underline{Y}$ 当且仅当 $X \cap Y = \varnothing$。\ > > (2) 设 $Z = XY$，则 $\underline{Z} = \underline{X} \cdot \underline{Y}$ 当且仅当 > > $$ > > \forall x, x' \in X, y, y' \in Y, (xy = x' y' \Rightarrow x = x', y = y') > > $$ > > (3) 若 $X \subset A^+$，令 $P = X^*$，则 $\underline{P} = \underline{X}^*$ 当且仅当 $X$ 为码。 _Proof._ 在 $\text{char } K = 0$ 的条件下，考虑形式级数运算的组合意义： > (1) $\underline{Z} = \underline{X} + \underline{Y}$ 无非是说 $z \in Z$ 当且仅当 $z \in X, z \in Y$ 恰居其一。\ > (2) $\underline{Z} = \underline{X} \cdot \underline{Y}$ 无非是说 $z \in Z$ 存在唯一分解 $z = xy \ (x \in X, y \in Y)$。\ > (3) $\underline{P} = \underline{X}^*$ 无非是说 $w \in P$ 存在唯一分解 $w = x_1 \cdots x_n \ (n \in \mathbb{N}, x_i \in X)$，由 **命题 1.2.2** 可见这等价于 $X$ 为码。 ### References 1. M. Lothaire, _Combinatorics on Words_, Cambridge Mathematical Library, Cambridge University Press, 1997 reprint of the 1983 edition, Chapter 1.