Vì bạn không chỉ định định dạng nhập, tôi giả định rằng 0 là trạng thái ban đầu, bất kỳ số nguyên nào xuất hiện trong cột thứ hai nhưng không phải là số nguyên đầu tiên chấp nhận trạng thái (3 cho T1 và 2 cho T2), và mỗi hàng là một phần tử của quan hệ chuyển tiếp, cho trạng thái trước đó, trạng thái tiếp theo, ký tự đầu vào và chữ cái đầu ra. Mọi hoạt động trên FST cần tạo ra một FST mới, vì vậy chúng ta cần các trạng thái, một bảng chữ cái đầu vào, bảng chữ cái đầu ra, trạng thái ban đầu, trạng thái cuối cùng và quan hệ chuyển đổi (các đặc tả của FST A, B và W dưới đây là được đưa ra theo thứ tự này). Giả sử FSTs của chúng tôi là:
A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)
và chúng tôi muốn tìm
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
Lưu ý rằng chúng tôi không cần phải xác định các bảng chữ cái của W; định nghĩa về bố cục thực hiện điều đó.
Hãy tưởng tượng chạy A và B theo chuỗi, với băng đầu ra của A được nạp dưới dạng băng đầu vào của B. Trạng thái của FST kết hợp đơn giản là các trạng thái kết hợp của A và B. Nói cách khác, các trạng thái của bố cục nằm trong sản phẩm chéo của các trạng thái của các FST riêng rẽ.
R = Q × P
Trong ví dụ của bạn, các bang W sẽ là cặp số nguyên:
R = {(0,0), (0,1), ... (3, 2)}
mặc dù chúng ta có thể ghi số lại những điều này và nhận được (ví dụ):
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
Tương tự như vậy, ban đầu và chấp nhận các tiểu bang của FST sáng tác là các sản phẩm chéo của những người trong FST thành phần. Đặc biệt, R chấp nhận một chuỗi iff A và B đều chấp nhận chuỗi.
R0 = Q0 × P0
RF = QF × PF
Trong ví dụ này, R = {00} và R F = {32}.
Tất cả những gì còn lại là xác định mối quan hệ chuyển tiếp ω. Đối với điều này, hãy kết hợp từng quy tắc chuyển đổi cho A với mọi quy tắc chuyển đổi cho B có thể áp dụng. Tức là, kết hợp từng quy tắc chuyển đổi của A (qi, σ) → (qj, γ) với mọi quy tắc của B có ký tự "γ" làm ký tự nhập.
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
Trong ví dụ, điều này có nghĩa là kết hợp (ví dụ:) 0 1 a : b của T1 với 0 1 b : a và 1 2 b : a của T2 để có được:
00 11 a : a
01 12 a : a
Tương tự như vậy, bạn muốn kết hợp 0 2 b : b của T1 với những người cùng 0 1 b : a và 1 2 b : a của T2, 0 0 a : a của T1 với 1 1 a : d và 1 2 a : c của T2 & c.
Lưu ý rằng bạn có thể có trạng thái không thể truy cập (những trạng thái không bao giờ xuất hiện ở trạng thái "tiếp theo") và chuyển tiếp sẽ không bao giờ xảy ra (những trạng thái không thể truy cập). Là bước tối ưu hóa, bạn có thể xóa các trạng thái và chuyển tiếp đó. Tuy nhiên, để chúng trong sẽ không ảnh hưởng đến tính chính xác của công trình; nó chỉ đơn giản là một tối ưu hóa.