Ponieważ nie określiłeś formatu wejściowego, zakładam, że 0 jest stanem początkowym, wszystkie liczby całkowite, które pojawiają się w drugiej kolumnie, ale nie są stanami akceptującymi (3 dla T1 i 2 dla T2), a każdy wiersz jest elementem relacji przejściowej, dając poprzedni stan, następny stan, literę wejściową i literę wyjściową.
Każda operacja na FST musi wytworzyć nowe FST, więc potrzebujemy stanów, alfabetu wejściowego, wyjściowego alfabetu, stanów początkowych, stanów końcowych i relacji przejściowej (specyfikacje FST A, B i W poniżej są podana w tej kolejności). Załóżmy nasze FSTS są:
A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)
i chcemy znaleźć
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
pamiętać, że nie ma potrzeby, aby określić alfabetów o W; definicja składu to robi.
Wyobraź sobie, że działa się szeregowo A i B, a taśma wyjściowa A jest podawana jako taśma wejściowa B. Stan połączonego FST jest po prostu połączonymi stanami A i B. Innymi słowy, stany kompozycji są w produkcie krzyżowym stanów poszczególnych FST.
R = Q × P
W przykładzie stany W byłyby pary liczb:
R = {(0,0), (0,1), ... (3, 2)}
chociaż moglibyśmy zmienić numerację tych i get (na przykład):
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
Podobnie, początkowe a stany przyjmujące złożonego FST są produktami krzyżowymi tych w składowych FST. W szczególności R akceptuje ciąg znaków iff A i B, które akceptują ciąg znaków.
R0 = Q0 × P0
RF = QF × PF
W przykładzie R = {00} i R F = {32}.
Pozostaje tylko ustalić związek przejściowy ω. W tym celu połącz każdą regułę przejścia dla A z każdą regułą przejścia dla B, która może mieć zastosowanie. To znaczy, połącz każdą regułę przejścia A (qi, σ) → (qj, γ) z każdą regułą B, która ma "γ" jako znak wejściowy.
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
W przykładzie oznacza to łączenie (np.) 0 1 a : b T1 z 0 1 b : a i 1 2 b : a T2 dostać:
00 11 a : a
01 12 a : a
Podobnie, można by połączyć 0 2 b : b T1 z tych samych 0 1 b : a i 1 2 b : a T2, 0 0 a : a T1 z 1 1 a : d i 1 2 a : c T2 & C.
Pamiętaj, że możesz mieć nieosiągalne stany (te, które nigdy nie pojawiają się jako "następny" stan) i przejścia, które nigdy nie wystąpią (te z nieosiągalnych stanów). Jako krok optymalizacji możesz usunąć te stany i przejścia. Pozostawienie ich nie wpłynie jednak na prawidłowość konstrukcji; to po prostu optymalizacja.