Поскольку вы не указали формат ввода, я предполагаю, что 0 является начальным состоянием, любые целые числа, которые появляются во втором столбце, но не в первом, принимают принимаемые состояния (3 для T1 и 2 для T2), и каждая строка является элементом отношения перехода, в котором указаны предыдущее состояние, следующее состояние, буква ввода и буква вывода.
Любая операция над FST должна производить новый FST, поэтому нам нужны состояния, входной алфавит, выходной алфавит, начальные состояния, конечные состояния и отношение перехода (приведены спецификации FST A, B и W ниже). в этом порядке). Предположим, что наши FST:
A = (Q, Σ, Γ, Q<sub>0</sub>, Q<sub>F</sub>, α)
B = (P, Γ, Δ, P<sub>0</sub>, P<sub>F</sub>, β)
и мы хотим найти
W = (R, Σ, Δ, R<sub>0</sub>, R<sub>F</sub>, ω) = A ∘ B
Обратите внимание, что нам не нужно определять алфавиты W; определение состава делает это.
Представьте себе, что А и В работают последовательно, а выходная лента А подается в качестве входной ленты В. Состояние объединенного 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 принимает строку , если A и B принимают строку.
R<sub>0</sub> = Q<sub>0</sub> × P<sub>0</sub>
R<sub>F</sub> = Q<sub>F</sub> × P<sub>F</sub>
В этом примере R 0 = {00} и R F = {32}.
Осталось только определить переходное отношение ω. Для этого объедините каждое правило перехода для A с каждым применимым правилом перехода для B. То есть, объедините каждое правило перехода A (q<sub>i</sub>, σ) → (q<sub>j</sub>, γ) с каждым правилом B, которое имеет «γ» в качестве входного символа.
ω = { ((q<sub>i</sub>,p<sub>h</sub>), σ) → ((q<sub>j</sub>, p<sub>k</sub>), δ) : (q<sub>i</sub>, σ) → (q<sub>j</sub>, γ) ∈ α,
(p<sub>h</sub>, γ) → (p<sub>k</sub>, δ) ∈ β}
В данном примере это означает объединение (например) 0 1 a : b T1 с 0 1 b : a и 1 2 b : a T2 для получения:
00 11 a : a
01 12 a : a
Аналогично, вы бы объединили 0 2 b : b T1 с теми же 0 1 b : a и 1 2 b : a T2, 0 0 a : a T1 с 1 1 a : d и 1 2 a : c T2 и т.
Обратите внимание, что у вас могут быть недоступные состояния (те, которые никогда не появляются как «следующее» состояние) и переходы, которые никогда не произойдут (те из недоступных состояний). В качестве шага оптимизации вы можете удалить эти состояния и переходы. Однако, оставляя их, это не повлияет на правильность конструкции; это просто оптимизация.