考慮以下FSTS：如何執行FST（有限狀態傳感器）組成
T1
0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a
T2
0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c
如何在這兩個FSTS進行合成操作（即T1ØT2） 我看到了一些算法，但couldn」不太瞭解。如果任何人都能以簡單的方式解釋它，這將是一個重大的幫助。
請注意，這不是一項家庭作業。這個例子是從給出解決方案的演講幻燈片中提取的，但我無法弄清楚如何實現它。
由於您沒有指定輸入格式，因此我假定0是初始狀態，任何出現在第二列但不是第一列的整數都是接受狀態（3代表T1，2代表T2），每行都是過渡關係的一個元素，給出了之前的狀態，下一個狀態，輸入字母和輸出字母。
FST上的任何操作都需要生成一個新的FST，所以我們需要狀態，輸入字母表，輸出字母表，初始狀態，最終狀態和轉換關係（下面的FST A，B和W的規格是按此順序給出）。假設我們的FSTS是：
A = (Q, Σ, Γ, Q0, QF, α) B = (P, Γ, Δ, P0, PF, β)
，我們希望找到
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
請注意，我們並不需要確定W的字母;組合的定義就是這樣做的。
想象一下將A和B串聯運行，A的輸出磁帶作爲B的輸入磁帶饋送。組合FST的狀態只是A和B的組合狀態。換句話說，組成狀態是各個FST狀態的叉積。
R = Q × P
在您的例子，W的狀態將是整數的對：
R = {(0,0), (0,1), ... (3, 2)}
雖然我們可以重新編排這些並獲得（例如）：
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
同樣，初始並且接受組合FST的狀態是組件FST中的那些的交叉產物。特別是，R接受一個字符串iff A和B都接受該字符串。
R0 = Q0 × P0 RF = QF × PF
在該示例中，R 0 = {00}和R ˚F = {32}。
剩下的就是確定過渡關係ω。爲此，將A的每個轉換規則與可能適用的B的每個轉換規則結合起來。即將A (qi, σ) → (qj, γ)的每個轉換規則與具有「γ」的每個B規則組合爲輸入字符。
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
在該示例中，這意味着組合（例如，）T1的0 1 a : b與0 1 b : a和T2的1 2 b : a獲得：
00 11 a : a 01 12 a : a
同樣，你會結合T1的0 2 b : b與那些同樣0 1 b : a和T2的1 2 b : a，0 0 a : a T1與1 1 a : d和T2 &的C 1 2 a : c。
請注意，您可能有無法訪問的狀態（永遠不會顯示爲「下一個」狀態的狀態）和永遠不會發生的狀態（來自不可訪問狀態的狀態）。作爲優化步驟，您可以刪除這些狀態和轉換。但是，將它們留在不會影響施工的正確性;這只是一個優化。
如果您更喜歡圖形化的解釋，下面的一組幻燈片提供了實際中組成算法的增量圖形化示例，還包括組件換能器中ε變化的討論。 Epsilon轉換會使合成過程變得複雜，並且在這種情況下，outis answer中描述的算法可能無法產生正確的結果，具體取決於所使用的semiring。
見幻燈片10〜35爲一些圖形的例子：