Como no especificó el formato de entrada, asumo que 0 es el estado inicial, cualquier entero que aparezca en la segunda columna pero no el primero son estados aceptables (3 para T1 y 2 para T2), y cada fila es un elemento de la relación de transición, dando el estado anterior, el siguiente estado, la letra de entrada y la letra de salida.
Cualquier operación en FST necesita producir una nueva FST, por lo que necesitamos estados, un alfabeto de entrada, un alfabeto de salida, estados iniciales, estados finales y una relación de transición (las especificaciones de las FST A, B y W a continuación son dado en este orden). Supongamos que nuestro FST son:
A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)
y queremos encontrar
W = (R, Σ, Δ, R0, RF, ω) = A ∘ B
Tenga en cuenta que no es necesario para determinar los alfabetos de W; la definición de composición hace eso.
Imagínese funcionamiento A y B en serie, con cinta de salida de A alimentado como cinta de entrada de B. El estado de la combinado FST es simplemente los estados combinados de A y B. En otras palabras, los estados de la composición están en el producto vectorial de los estados de los FSTs individuales.
R = Q × P
En su ejemplo, los estados de W serían pares de números enteros:
R = {(0,0), (0,1), ... (3, 2)}
aunque no pudimos renumerar estos y obtener (por ejemplo):
R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}
Del mismo modo, inicial y los estados de aceptación del FST compuesto son los productos cruzados de aquellos en el componente FST. En particular, R acepta una cadena iff A y B ambas aceptan la cadena.
R0 = Q0 × P0
RF = QF × PF
En el ejemplo, R = {00} y R F = {32}.
Todo lo que queda es determinar la relación ω transición. Para esto, combine cada regla de transición para A con cada regla de transición para B que pueda aplicarse. Es decir, se combinan cada regla de transición de A (qi, σ) → (qj, γ) con todas las reglas de B que tiene un "γ" como el carácter de entrada.
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
En el ejemplo, esto significa combinar (p. Ej.) 0 1 a : b de T1 con 0 1 b : a y 1 2 b : a de T2 para obtener:
00 11 a : a
01 12 a : a
Del mismo modo, usted debe combinar 0 2 b : b de T1 con los mismos 0 1 b : a y 1 2 b : a de T2, T1 con 0 0 a : a de 1 1 a : d1 2 a : c y de T2 & c.
Tenga en cuenta que puede tener estados inalcanzables (los que nunca aparecen como un estado "siguiente") y transiciones que nunca ocurrirán (aquellas de estados inalcanzables). Como paso de optimización, puede eliminar esos estados y transiciones. Sin embargo, dejarlos no afectará la corrección de la construcción; es simplemente una optimización.