Weighted Finite-State Transducer

总结来源于此。

加粗圈代表初始状态（0）；普通圈代表中间状态（1,2）；双圈代表终止状态（3）。

1. ∑ 是输入集合                                                                                    ∑ = {a, b, c, d}

2. ∆ 是输出集合                                                                                    ∆  = {A, B, C, D}   

3. Q 是所有的状态集合                                                                         Q = {1, 2, 3, 4}                      

4. I ⊆ Q 是初始状态集合，Openfst中一般只有1个                                I = {0}

5. F ⊆Q 是终止状态集合， 通常有1个或多个                                        F = {3}

6. E⊆Q×(∑∪{ε})×(∆∪{ε})×K×Q 代表所有状态之间的转移集合             E = {a:A/1, b:C/1.5, c:B/0.3, d:D/2}

7. λ : I → K 是初始状态的权重                                                                λ(0) = 0,2

8. ρ : F →K 是终止状态的权重                                                                ρ(3) = 0.5

给定WFST =(∑,∆,Q,I,F,E,λ,ρ)， 对任意状态q ∈Q, E[q]为从q出发的所有转移集合

q = 0                E[q] = {a:A/1, b:C/1.5}

q = 1                E[q] = {c:B/0.3}

q = 2                E[q] = {d:D/2}

对于每个转移 e ∈ E, 输入label是 i[e], 输出label是o[e], 出发状态 p[e], 到达状态 n[e], 转移上的权重 w[e]. 

例如  e = a:A/1            i[e] = a;        o[e] = A;        p[e] = 0;        n[e] = 1;        w[e] = 1

一系列转移组成路径 π = e1, … , ek ， 明显可以知道 n[ej−1] = p[ej ] 对于 j = 2,…,k. 用 n[·] 和p[·] 表示路径 n[π] = n[ek] 及 p[π] = p[e1].

例如    π = a:A/1, c:B/0.3            p[π] = p[e1] = 0;        n[π] = n[ek] = 3

如果路径中n[e1]∈I 并且n[ek ] ∈ F， 则这条路径叫做 successful path

如果一个状态能通过一系列转移从起点到达并且能通过转移到达某个终点，这个状态是coaccessible的， 所有coaccessible的状态都在至少一条successful path上。 其他状态叫做dead states。去除所有dead states这一操作叫做trimming或者 connect，Openfst的中wfst的Connect的算法（仅一次遍历整个图）是使用Tarjan’s Algorithm寻找最大强连通域SCC。