Как выполнить FST (Преобразователь Конечного состояния) состав
Рассмотрите следующий FSTs:
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 o T2), я видел некоторые алгоритмы, но не мог понять много. Если бы кто-либо мог бы объяснить это в простом способе, это была бы главная справка.
Обратите внимание на то, что это не домашняя работа. Пример взят от слайдов лекции, где решение дано, но я не мог выяснить, как добраться до него.
1 ответ
Поскольку вы не указали формат ввода, я предполагаю, что 0 - это начальное состояние, любые целые числа, которые появляются во втором столбце, но не сначала принимают состояния (3 для T1 и 2 для T2), и каждая строка является элементом отношения перехода, дающим предыдущее состояние, следующее состояние, входную букву и выходную букву.
Любая операция с FST должна приводить к созданию нового FST, поэтому нам нужны состояния, входной алфавит, выходной алфавит, начальные состояния, конечные состояния и отношение перехода (спецификации FST A, B и W ниже приведены в этом порядке). Предположим, что наши FST:
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 принимает строку , если и только если A и B оба принимают строку.
R0 = Q0 × P0 RF = QF × PF
В этом примере R 0 = {00} и R F = {32}.
Все, что остается, - это определить отношение перехода ω. Для этого объедините каждое правило перехода для A с каждым правилом перехода для B, которое может применяться. То есть объедините каждое правило перехода A (q i , σ) → (q j , γ) с каждым правилом B, имеющим "γ "как входной символ.
ω = { ((qi,ph), σ) → ((qj, pk), δ) : (qi, σ) → (qj, γ) ∈ α,
(ph, γ) → (pk, δ) ∈ β}
В примере это означает объединение (например) 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 и c.
Обратите внимание, что у вас могут быть недостижимые состояния (те, которые никогда не появляются как «следующее» состояние) и переходы, которые никогда не произойдут (из недостижимых состояний). В качестве шага оптимизации вы можете удалить эти состояния и переходы. Однако их оставление не повлияет на правильность конструкции; это просто оптимизация.