加权自动机：在 Semirings 上建模

参考文献：

1. Handbook of weighted automata[M]. Springer Science & Business Media, 2009.
2. Heinz J. Syntax and Semantics of MSO and FO Logics[J]. 2019.
3. FSM, FAM, DFA, NFA 的区别与联系-CSDN博客
4. 形式语言与自动机理论 - 知乎 (zhihu.com)
5. 基本等价式、基本蕴含式-CSDN博客
6. 柯西乘积（级数乘法） - 知乎 (zhihu.com)

幺半群（Monoids）

幺半群：结构是 $(M,\cdot ,1)$，非空集合 $M$，二元运算 $\cdot$，幺元 $1$，

1. 二元运算是封闭的，$\forall m_1,m_2\in M,m_1\cdot m_2\in M$
2. 二元运算是结合的，$(m_1\cdot m_2)\cdot m_3=m_1\cdot (m_2\cdot m_3)$
3. 存在幺元（neutral element），$\forall m\in M,1\cdot m=m\cdot 1=m$

如果 $m_1\cdot m_2=m_2\cdot m_1,\forall m_1,m_2\in M$，我们说它是交换的。一般地，交换幺半群记为 $(M,+,0)$。幺半群，可以视为不存在减法的群。

Kleene-iteration：给定集合 $V$，“Kleene star” 是对集合的一元运算 ，定义为
$$V^{\ast }=\bigcup _{n\in \mathbb{N}}{V}^n$$

其中 V 0 = { ϵ } V^0=\{\epsilon\} V0={ϵ}，迭代计算 V i + 1 = { w v ∣ w ∈ V i , v ∈ V } V^{i+1}=\{wv|w \in V^i,v \in V\} Vi+1={wv∣w∈Vi,v∈V}，它是有限长字符串的集合。常用在正则表达式中。

字母表（alphabet） $\Sigma$ 是非空集合，$x_i\in \Sigma$ 叫做字母（letters），$w=x_1\cdots x_n\in {\Sigma }^{\ast }$ 叫做单词（words），长度（length） $|w|=n$。当 $n=0$ 叫做空单词（empty word），简记为 $ϵ$，注意与空集 $\varnothing$ 做区分 { ϵ } ≠ ∅ \{\epsilon\} \neq \empty {ϵ}=∅

自由幺半群（free monoid）：给定字母表 $\Sigma$，形如 $({\Sigma }^{\ast },\cdot ,ϵ)$，单词的乘法定义为级联 $w_1\cdot w_2=w_1{w}_2\in {\Sigma }^{\ast }$

态射（morphism）：字母表 $\Sigma$，半群 $(M,\cdot ,1)$，半群 $({\Sigma }^{\ast },\cdot ,ϵ)$，任意的映射 $h:\Sigma \to M$，可以被唯一地扩展为幺半群的同态 $h^{\#}:{\Sigma }^{\ast }\to M$，
h # ( ϵ ) = 1 h # ( x 1 ⋯ x n ) = h ( x 1 ) ⋯ h ( x n ) h#(ϵ)=1h#(x1⋯xn)=h(x1)⋯h(xn)

h#(ϵ)h#(x1​⋯xn​)​=1=h(x1​)⋯h(xn​)​

对于一个交换幺半群 $(M,+,0)$，

• 幂等的（idempotent）：如果 $\forall m\in M,m+m=m$
• 有序的（ordered）：如果装备了偏序关系 $\le$，且 $+$ 保持偏序关系
• 正有序的（positively ordered）：携带 $\le$ 的有序幺半群，满足 $0\le m,\forall m\in M$
• 自然有序的（naturally ordered）：如果定义由 $+$ 诱导的关系 $ m_1 \sqsubseteq m_2 \iff m_1+m=m_2,\exists m \in M$，它是个偏序关系

完备幺半群（complete monoid）：幺半群 $(M,+,0)$，令 $I$ 是任意的指标集，定义无穷加法（infinitary sum operation）${\sum }_I:M^I\to M$。我们说幺半群是完备的，如果
∑ i ∈ ∅ m i = 0 ∑ i ∈ { j } m i = m j ∑ i ∈ { j , k } m i = m j + m k ,    j ≠ k ∑ j ∈ J ∑ i ∈ I j m i = ∑ I m j ,    I = ⋃ j ∈ J I j ,    I j ∩ I j ′ = ∅ , ∀ j ≠ j ′ ∑i∈\emptymi=0∑i∈{j}mi=mj∑i∈{j,k}mi=mj+mk,j≠k∑j∈J∑i∈Ijmi=∑Imj,I=⋃j∈JIj,Ij∩Ij′=\empty,∀j≠j′

i∈∅∑​mi​i∈{j}∑​mi​i∈{j,k}∑​mi​j∈J∑​i∈Ij​∑​mi​​=0=mj​=mj​+mk​,j=k=I∑​mj​,I=j∈J⋃​Ij​,Ij​∩Ij′​=∅,∀j=j′​

也就是说把（无限大）指标集 $I$ 任意打乱顺序 “加括号”，不改变加和的计算结果。明显的，完备性导致交换性；反之，交换幺半群不一定是完备的。

半环（Semirings）

半环：结构是 $(S,+,\cdot ,0,1)$，非空集合 $S$，二元运算 $+,\cdot$，零元 $0$，幺元 $1$，

1. $(S,+,0)$ 是交换幺半群
2. $(S,\cdot ,1)$ 是幺半群
3. 满足左右分配律，$(a+b)\cdot c=a\cdot c+b\cdot c$ 以及 $c\cdot (a+b)=c\cdot a+c\cdot b$
4. 存在零元，$0\cdot a=a\cdot 0=0,\forall a\in a$

如果 $(S,\cdot ,1)$ 是交换的，我们说半环是交换的。如果 $(S,+,0)$ 是幂等的，我们说半环是幂等的。如果 $(S,+,0)$ 是（正）有序的，我们说半环是**（正）有序的**。如果 $(S,+,0)$ 是完备的，我们说半环是完备的。半环，可以视为不存在减法的含幺环。

半环的例子：

• 布尔半环（Boolean semiring） B = { 0 , 1 } \mathbb B=\{0,1\} B={0,1}，携带 OR、AND 运算，$1+1=1,1\cdot 1=1$
• 所有的含幺环（$\mathbb{Z}$）、所有的域（$\mathbb{Q},\mathbb{R},\mathbb{C}$），携带的运算是自然的
• 定义 N ∞ : = N ∪ { ∞ } \mathbb N^\infty:=\mathbb N \cup\{\infty\} N∞:=N∪{∞} 以及 N ‾ : = N ∪ { − ∞ , ∞ } \overline{\mathbb N}:=\mathbb N \cup\{-\infty,\infty\} N:=N∪{−∞,∞}，并规定 $0\cdot \infty =\infty \cdot 0=0$ 以及 $(-\infty )+\infty =-\infty$
  • $({\mathbb{N}}^{\infty },+,\cdot ,0,1)$
  • $({\mathbb{N}}^{\infty },\min ,+,\infty ,0)$，称为 tropical/min-plus semirings
  • $(\overline{\mathbb{N}},\max ,+,-\infty ,0)$，称为 arctic/max-plus semirings
• 定义 R + : = { a ∈ R ∣ a ≥ 0 } \mathbb R_+:=\{a \in \mathbb R|a \ge 0\} R+​:={a∈R∣a≥0}， R + ∞ : = R + ∪ { ∞ } \mathbb R_+^\infty:=\mathbb R_+ \cup\{\infty\} R+∞​:=R+​∪{∞} 以及 R ‾ + : = R + ∪ { − ∞ , ∞ } \overline{\mathbb R}_+:=\mathbb R_+ \cup\{-\infty,\infty\} R+​:=R+​∪{−∞,∞}，
  • $({\mathbb{R}}_{+},+,\cdot ,0,1)$，
  • $({\mathbb{R}}_{+}^{\infty },+,\cdot ,0,1)$
  • $({\mathbb{R}}_{+}^{\infty },\min ,+,\infty ,0)$，称为 tropical/min-plus semirings
  • $({\overline{\mathbb{R}}}_{+},\max ,+,-\infty ,0)$，称为 arctic/max-plus semirings
• 维特比半环（Viterbi semiring）$([0,1],\max ,\cdot ,0,1)$

令 $\Sigma$ 是有限字母表，任意子集 $L\subseteq {\Sigma }^{\ast }$ 被称为形式语言（formal language），定义语言的乘积（单词的级联）
L 1 ⋅ L 2 = { w 1 w 2 ∣    w 1 ∈ L 1 , w 2 ∈ L 2 } L_1 \cdot L_2 = \{w_1w_2|\,\, w_1 \in L_1,w_2 \in L_2\} L1​⋅L2​={w1​w2​∣w1​∈L1​,w2​∈L2​}

集合 $U$ 的幂集（power set）定义为所有子集的收集，简记为 $2^U$。那么 ${\Sigma }^{\ast }$ 的幂集 ( 2 Σ ∗ , ∪ , ⋅ , ∅ , { ϵ } ) (2^{\Sigma^*},\cup,\cdot,\empty,\{\epsilon\}) (2Σ∗,∪,⋅,∅,{ϵ}) 是一个半环，称为形式语言半环（semiring of formal languages）。

集合 $U$ 上的二元关系（binary relation）可以表示为子集 $R\subseteq U\times U$，我们定义二元关系的乘积
$$R_1\cdot R_2=\{(u_1,u_2)|\exists u\in U,(u_1,u)\in R_1,(u_2,u)\in R_2\}$$

易知幂集 $2^{U\times U}$ 是所有二元关系的收集，定义关系 $\Delta =\{(u,u)|u\in U\}$，那么 $(2^{U\times U},\cup ,\cdot ,\varnothing ,\Delta )$ 是一个半环，称为二元关系半环（semiring of binary relations）

偏序集（partially ordered set）$(L,\le )$，定义二元运算：最小上界（least upper bound） a ∨ b : = sup ⁡ { a , b } a \vee b:=\sup\{a,b\} a∨b:=sup{a,b}、最大下界（greatest lower bound） a ∧ b : = inf ⁡ { a , b } a \wedge b:=\inf\{a,b\} a∧b:=inf{a,b}，假如 $\forall a,b\in L$ 使得 $a\vee b\in L,a\wedge b\in L$ 总存在，那么称为格（lattice）。我们说它是分配的（distributive），如果 $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c),\forall a,b,c$；我们说它是有界的（bounded），如果存在最小元（smallest element，记为 $0$）和最大元（greatest element，记为 $1$）。给定任意的有界分配格，那么 $(L,\vee ,\wedge ,0,1)$ 是半环。给定任意的分配格，那么 $(L,\wedge ,\vee ,1,0)$ 是半环。

形式幂级数

给定字母表 $\Sigma$ 和半环 $S$，映射 $r:{\Sigma }^{\ast }\to S$ 叫做形式幂级数（formal power series），我们将单词 $w$ 的像记作 $r(w):=(r,w)\in S$，把映射写作 formal sum 的形式
$$r=\sum _{w\in {\Sigma }^{\ast }}(r,w)w$$

其中的 $(r,w)$ 叫做系数。非零系数的单词叫做支撑（support），它是集合
s u p p ( r ) = { w ∈ Σ ∗ ∣ ( r , w ) ≠ 0 S } supp(r) = \{w \in \Sigma^*| (r,w) \neq 0_S\} supp(r)={w∈Σ∗∣(r,w)=0S​}

我们定义一些关于幂级数的集合：

1. 所有幂级数的收集，记为 $S⟨⟨{\Sigma }^{\ast }⟩⟩$
2. 有限支撑的幂级数被称为多项式，它们的收集记为 $S⟨{\Sigma }^{\ast }⟩\subseteq S⟨⟨{\Sigma }^{\ast }⟩⟩$
   • 多项式 $r=0$，满足 $(0,w)=0,\forall w$，于是有 $supp(0)=\varnothing$
   • 多项式 $r=aw,a\ne 0_S$，满足 $(aw,w)=a$ 并且 $(aw,w^{\prime })=0,\forall w^{\prime }\ne w$，于是有 s u p p ( a w ) = { w } supp(aw)=\{w\} supp(aw)={w}
3. 那些 s u p p ( r ) ⊆ Σ ∪ { ϵ } supp(r) \subseteq \Sigma \cup \{\epsilon\} supp(r)⊆Σ∪{ϵ} 的多项式收集，记为 S ⟨ Σ ∪ { ϵ } ⟩ ⊆ S ⟨ Σ ∗ ⟩ S\langle \Sigma \cup \{\epsilon\} \rangle \subseteq S\langle \Sigma^* \rangle S⟨Σ∪{ϵ}⟩⊆S⟨Σ∗⟩
4. 类似的还有 S ⟨ Σ ⟩ , S ⟨ { ϵ } ⟩ S\langle\Sigma\rangle,S\langle\{\epsilon\}\rangle S⟨Σ⟩,S⟨{ϵ}⟩ 等等

如果 $r\in S⟨⟨{\Sigma }^{\ast }⟩⟩$ 的系数要么是 $0_S$ 要么是 $1_S$，称它是语言 $L=supp(r)\subseteq {\Sigma }^{\ast }$ 的特征级数（characteristic series），简记为 $r=char(L)$ 或者 $r=1_L$

• 语言 $\varnothing$ 的特征级数是 $char(\varnothing )=0$
• 语言 { w } , ∀ w ∈ Σ ∗ \{w\},\forall w \in \Sigma^* {w},∀w∈Σ∗ 的特征级数是 c h a r ( { w } ) = w char(\{w\}) = w char({w})=w

类似于幂级数 ${\sum }_n{a}_n$ 的运算，形式幂级数也有类似的运算，令 $+,\cdot$ 是半环 $S$ 的二元运算，

1. 加法（sum）$r_1+r_2$，定义为
   $$(r_1+r_2,w)=(r_1,w)+(r_2,w)$$

2. 柯西乘法（cauchy product）$r_1\cdot r_2$，定义为
   $$(r_1\cdot r_2,w)=\sum _{w_1{w}_1=w}(r_1,w_1)\cdot (r_2,w_2)$$

3. 阿达玛乘法（Hadamard product）$r_1\odot r_2$，定义为
   $$(r_1\odot r_2,w)=(r_1,w)\cdot (r_2,w)$$

4. 标量乘法（scalar product）$ar,ra$，定义为
   $$\begin{gathered} (ar,w)=a\cdot (r,w) \\ (ra,w)=(r,w)\cdot a \end{gathered}$$

可以验证，$(S⟨⟨{\Sigma }^{\ast }⟩⟩,+,\cdot ,0,ϵ)$ 和 $(S⟨{\Sigma }^{\ast }⟩,+,\cdot ,0,ϵ)$ 都是半环，这里的 $0=char(\varnothing )$ 和 ϵ = c h a r ( { ϵ } ) \epsilon=char(\{\epsilon\}) ϵ=char({ϵ}) 都是幂级数。并且 $(S⟨⟨{\Sigma }^{\ast }⟩⟩,+,\odot ,0,char({\Sigma }^{\ast }))$ 作为 $(S,+,\cdot ,0,1)$ 的完全笛卡尔积，也是半环。

令 $\mathbb{B}$ 是布尔代数，那么形式语言半环 ( 2 Σ ∗ , ∪ , ⋅ , ∅ , { ϵ } ) (2^{\Sigma^*},\cup,\cdot,\empty,\{\epsilon\}) (2Σ∗,∪,⋅,∅,{ϵ}) 同构于特征级数半环 $(\mathbb{B}⟨⟨{\Sigma }^{\ast }⟩⟩,+,\cdot ,0,ϵ)$，

• 同构映射 $\varphi :L\mapsto char(L)$，逆映射 ${\varphi }^{-1}:r\mapsto supp(r)$
• $r_1+r_2⟺L_1\cup L_2$
• $r_1\cdot r_2⟺L_1\cdot L_2$
• $r_1\odot r_2⟺L_1\cap L_2$

任意指标集 $I$，一族幂级数 { r i ∈ S ⟨ ⟨ Σ ∗ ⟩ ⟩ ∣    i ∈ I } \{r_i \in S\langle\langle \Sigma^* \rangle\rangle |\,\, i\in I\} {ri​∈S⟨⟨Σ∗⟩⟩∣i∈I}，定义 I w = { i ∣    ( r i , w ) ≠ 0 } I_w=\{i|\,\, (r_i,w) \neq 0\} Iw​={i∣(ri​,w)=0}，如果对于任意的 $w\in {\Sigma }^{\ast }$ 都使得 $I_w$ 是有限的，我们称这族幂级数是局部有限的（locally finite），此时我们可以在它上面定义幂级数的无穷加法 ${\sum }_{i\in I}{r}_i$，
$$\left(\sum _{i\in I}{r}_i,w\right)=\sum _{i\in I}(r_i,w),\forall w$$

如果幂级数 $r\in S⟨⟨{\Sigma }^{\ast }⟩⟩$ 满足 $(r,ϵ{)}^k=0,k>0$，称它是关于指标 $k$ 无环的（cycle-free of index k）。如果 $k$ 存在，我们称它是无环的。特别地，如果 $k=1$ 则称它是准正则的（proper/quasiregular）。

对无环幂级数 $r$，定义 star 一元运算 $r^{\ast }$，
$$r^{\ast }=\sum _{n\ge 0}{r}^n$$

这里的 $r^n$ 是连续 $n-1$ 个柯西乘积。可以证明 $(r^n,w)=0,\forall n\ge k\cdot (|w|+1)$，于是幂级数族 { r n ∣ n ≥ 0 } \{r^n| n\ge 0\} {rn∣n≥0} 是局部有限的，从而
$$(r^{\ast },w)=\sum _{0\le n<k\cdot (|w|+1)}(r^n,w)$$

因此 star 是 well-defined 的。而对于其他的幂级数，star 运算不一定是良的。

广义矩阵

令 $I,I^{\prime }$ 是任意的非空指标集，任意集合 $U$，那么矩阵（matrix）是一个映射 $A:I\times I^{\prime }\to U$，定义为 $(i,i^{\prime })\mapsto A_{i,i^{\prime }}$，我们称 $A_{i,i^{\prime }}$ 为矩阵的 $(i,i^{\prime })$-entry，全部的矩阵收集为 $U^{I\times I^{\prime }}$。如果 $I,I^{\prime }$ 都是有限的，称它是有限矩阵（finite matrix）。

令 $(S,+,\cdot ,0,1)$ 是半环，对于集合 $S^{I\times I^{\prime }}$ 定义矩阵加法 $A+B\in S^{I\times I^{\prime }}$，
$$(A+B{)}_{i,i^{\prime }}=A_{i,i^{\prime }}+B_{i,i^{\prime }}$$

定义零矩阵 $O$ 为 $O_{i,i^{\prime }}=0$，那么 $(S^{I\times I^{\prime }},+,O)$ 是交换幺半群。

对于矩阵 $A\in S^{I\times I^{\prime }}$，如果指标集 ∀ i ∈ I , { j ∣ A i j ≠ 0 } \forall i \in I,\{j|A_{ij} \neq 0\} ∀i∈I,{j∣Aij​=0} 都是有限的，我们称它是行有限的（row finite）。类似的，可定义列有限矩阵（column finite）。

如果 $A\in S^{I_1\times I_2}$ 是行有限的、或者 $B\in S^{I_2\times I_3}$ 是列有限的、又或者 $S$ 是完备的（这三种条件下，无穷加法是良的），定义矩阵乘法 $AB\in S^{I_1\times I_3}$，
$$(AB{)}_{i_1,i_3}=\sum _{i_2\in I_2}{A}_{i_1,i_2}{B}_{i_2,i_3}$$

定义单位阵 $E\in S^{I\times I}$ 为 $E_{ii}=1$ 且 $E_{ij}=0$，那么当 $I$ 是有限的、或者 $S$ 是完备的（可定义矩阵乘法），则 $(S^{I\times I},+,\cdot ,O,E)$ 是半环。而对于任意的半环 $S$ 和任意的指标集 $I$，全体的行有限矩阵和列有限矩阵组成的 $S^{I\times I}$ 的子集，也是半环。

加权自动机

在 Classical Automata 中，边的权重是 0/1，权重的运算是布尔逻辑 AND/OR，可用于判定 words 是否接受。而 Weighted Automata 是它的扩展，额外计算了 words 的代价、概率等信息。

给定任意的半环 $S$ 和有限字母表 $\Sigma$，有限自动机（Finite Automation）是四元组 $\mathcal{A}=(Q,R,A,P)$,

1. 非空的有限状态集 Q = { q 1 , q 2 , ⋯   , q n } Q=\{q_1,q_2,\cdots,q_n\} Q={q1​,q2​,⋯,qn​}
2. 转移矩阵（transition matrix） A ∈ ( S ⟨ Σ ∪ { ϵ } ⟩ ) Q × Q A \in (S\langle\Sigma \cup\{\epsilon\}\rangle)^{Q \times Q} A∈(S⟨Σ∪{ϵ}⟩)Q×Q
3. 初始状态行矢（initial state） R ∈ ( S ⟨ Σ ∪ { ϵ } ⟩ ) 1 × Q R \in (S\langle\Sigma \cup\{\epsilon\}\rangle)^{1 \times Q} R∈(S⟨Σ∪{ϵ}⟩)1×Q
4. 终止状态列矢（final state） P ∈ ( S ⟨ Σ ∪ { ϵ } ⟩ ) Q × Q P \in (S\langle\Sigma \cup\{\epsilon\}\rangle)^{Q \times Q} P∈(S⟨Σ∪{ϵ}⟩)Q×Q

如果 $A$ 是无环矩阵，我们称 $\mathcal{A}$ 是无环的（cycle-free）。一般地，可以把无环有限自动机表示为有向图，

• 包含 $n$ 个节点，标记为 $q_1,\cdots ,q_n$
• 由 $R$ 赋予了每个节点初始权重（initial weight），由 $P$ 赋予了每个节点终止权重（final weight），而 $R_q{P}_q$ 称为节点权重
• 初始（终止）重量不是零（零映射 $(0,w)=0,\forall w\in {\Sigma }^{\ast }$）的节点，是起点/终点
• 如果 $A_{q_i,q_j}\ne 0_S$，那么存在从节点 $q_i$ 到节点 $q_j$ 的边，记为 $q_i\stackrel{A_{q_i,q_j}}{⟶}{q}_j$
• 有限支撑幂级数 $A_{q_i,q_j}$ 是边的重量，记为 $wt(q_i,A_{q_i,q_j},q_j)$
• 从 $q_i$ 到 $q_j$ 之间的 $k$ 条边首尾相连，叫做长度为 $k$ 的路径，定义路径的重量是所有边的重量乘积

上述的权重都是幂级数（从 ${\Sigma }^{\ast }$ 到 $S$ 的映射），权重的乘积就是幂级数的柯西乘积。集合 S ⟨ Σ ∪ { ϵ } ⟩ S\langle\Sigma \cup\{\epsilon\}\rangle S⟨Σ∪{ϵ}⟩ 上的有限矩阵的运算，所包含的 entry 的加法/乘法就是有限支撑幂级数半环 $(S⟨⟨{\Sigma }^{\ast }⟩⟩,+,\cdot ,0,ϵ)$ 中定义的幂级数加法/柯西乘积，而幂级数的运算依赖于最底层半环 $(S,+,\cdot ,0,1)$ 的二元运算。

转移矩阵 $A$ 的矩阵元是幂级数，矩阵的平方，
( A 2 ) q i , q j = ∑ q k ∈ Q A q i , q k A q k , q j ∈ ( S ⟨ Σ 2 ∪ Σ ∪ { ϵ } ⟩ ) Q × Q (A^2)_{q_i,q_j} = \sum_{q_k \in Q}A_{q_i,q_k}A_{q_k,q_j} \in (S\langle\Sigma^2\cup\Sigma\cup\{\epsilon\}\rangle)^{Q \times Q} (A2)qi​,qj​​=qk​∈Q∑​Aqi​,qk​​Aqk​,qj​​∈(S⟨Σ2∪Σ∪{ϵ}⟩)Q×Q

它是从 $q_i$ 到 $q_j$ 的所有长度恰好为 $2$ 的路径权重的加和。因此转移矩阵的 $k$ 次幂，
$$A^k\in (S⟨\bigcup _{0\le l\le k}{\Sigma }^l⟩{)}^{Q\times Q}$$

就是从 $q_i$ 到 $q_j$ 的所有长度恰好为 $k$ 的路径权重的加和。定义转移矩阵的 star 运算，
$$A^{\ast }=\sum _{k\ge 0}{A}^k\in (\in S⟨⟨{\Sigma }^{\ast }⟩⟩{)}^{Q\times Q}$$

这个矩阵记录了从 $q_i$ 到 $q_j$ 的所有路径的权重加和。我们定义无环自动机的行为（behavior），
$$\Vert \mathcal{A}\Vert =\sum _{q_i,q_j\in Q}{R}_{q_i}(A^{\ast }{)}_{q_i,q_j}{P}_{q_j}=R{A}^{\ast }P$$

容易看出 $\Vert \mathcal{A}\Vert \in S⟨⟨{\Sigma }^{\ast }⟩⟩$ 是个幂级数，它是 “从任意起点到任意终点，之间的所有路径权重的加和，再乘以对应的起始权重和终止权重，最后全部加和”。

换一个视角：转移矩阵是一个映射 $A:\Sigma \to S^{Q\times Q}$，定义为 $a\mapsto A(a)$，这里 $A(a{)}_{q_i,q_j}\in S$ 是转移（transition） $q_i\stackrel{a}{⟶}{q}_j$ 的权重。映射 $A$ 可以唯一地扩展为幺半群的同态 $A^{\#}:({\Sigma }^{\ast },\cdot ,ϵ)\to (S^{Q\times Q},\cdot ,E)$，这是标签（label）为 $w=a_1\cdots a_n$ 的路径的转移矩阵。易知，$(\Vert \mathcal{A}\Vert ,w)=R\cdot A^{\#}(w)\cdot P$，如果令 $A(ϵ)=E$ 那么 $(\Vert \mathcal{A}\Vert ,ϵ)=RP$ 是各个节点权重的加和。

我们说幂级数 $r\in \in S⟨⟨{\Sigma }^{\ast }⟩⟩$ 是可识别的（recognizable），如果存在加权有限自动机 $\mathcal{A}$ 使得 $r=\Vert \mathcal{A}\Vert$，定义 $Rec(S,{\Sigma }^{\ast })$ 是所有的可识别幂级数的收集。我们说两个无环自动机 $\mathcal{A},{\mathcal{A}}^{\prime }$ 是等价的（equivalent），如果它们识别的幂级数相同 $\Vert \mathcal{A}\Vert =\Vert {\mathcal{A}}^{\prime }\Vert$。由于幂级数 $r$ 的支撑 $L=supp(r)\subseteq 2^{{\Sigma }^{\ast }}$ 是某个语言，我们说识别 $r$ 的自动机可以识别这个语言。

我们说有限自动机 $\mathcal{A}=(Q,R,A,P)$ 是标准化的（normalized），如果 $n=|Q|\ge 2$，$q_1\ne q_n\in Q$，满足以下约束

1. 恰好一个起点：$R_{q_1}=ϵ$，并且 $R_q=0,\forall q\ne q_1$
2. 恰好一个终点：$P_{q_n}=ϵ$，并且 $P_q=0,\forall q\ne q_n$
3. 起点的入度为零：$A_{q,q_1}=0,\forall q\in Q$，也没有自己到自己的圈
4. 终点的出度为零：$A_{q_n,q}=0,\forall q\in Q$，也没有自己到自己的圈

任意的无环有限自动机都等价于某个标准化的无环有限自动机：给定无环自动机 $\mathcal{A}=(Q,R,A,P)$，那么构造一个新的自动机，
A ′ = ( { q 0 } ∪ Q ∪ { q n + 1 } ,    ( ϵ , 0 ⃗ , 0 ) ,    ( 0 R 0 0 A P 0 0 0 ) ,    ( 0 0 ⃗ ϵ ) ) \mathcal A' = \left( \{q_0\} \cup Q \cup \{q_{n+1}\},\,\, (ϵ,→0,0)

,\,\, (0R00AP000),\,\, (0→0ϵ) \right) A′= ​{q0​}∪Q∪{qn+1​},(ϵ,0 ,0​), ​000​RA0​0P0​ ​, ​00 ϵ​ ​ ​

其中 $q_0,q_{n+1}$ 是新添的状态。容易验证，新自动机是一个标准化的无环有限自动机，并且两者识别相同的语言。

经典自动机

假如半环使用的是布尔代数 $(\mathbb{B},+,\cdot ,0,1)$，再令 $R,A,P$ 是集合 $\mathbb{B}⟨\Sigma ⟩$ 上的矩阵，那么加权自动机 $\mathcal{A}=(Q,R,A,P)$ 就退化为了经典的有限自动机，

• 转移矩阵 $A:\Sigma \to {\mathbb{B}}^{Q\times Q}$，它将字母 $a$ 映射到矩阵 $A(a)\in S^{Q\times Q}$
• 矩阵元 $A(a{)}_{p,q}\in \mathbb{B}$ 是状态转移 $p\stackrel{a}{\to }q$ 的权重 w t ( p , a , q ) ∈ { 0 , 1 } wt(p,a,q) \in \{0,1\} wt(p,a,q)∈{0,1}
• 标签 w = a 1 ⋯ a n ∈ { 0 , 1 } n w=a_1\cdots a_n \in \{0,1\}^n w=a1​⋯an​∈{0,1}n 的路径 $P:q_0\stackrel{a_1}{\to }{q}_1\stackrel{a_2}{\to }\cdots \stackrel{a_n}{\to }{q}_n$ ，重量为 $wt(q_0,w,q_n)=R_{q_0}\cdot A(a_1{)}_{q_0,q_1}\cdots A(a_n{)}_{q_{n-1},q_n}\cdot P_{q_n}$

布尔代数 $\mathbb{B}$ 的二元运算是 OR/AND，因此：矩阵 $A^k$ 记录了长度为 $k$ 的某条路径是否通畅，而 $A^{\ast }$ 记录了任意两个状态之间是否存在通路。