Как выполнить композицию FST (Finite State Transducer)

Рассмотрим следующие FST:

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

Как мне выполнить операцию композиции на этих двух FST (то есть T1 или T2), я видел некоторые алгоритмы, но не мог понять многое. Если бы кто-нибудь мог объяснить это простым способом, это было бы серьезной помощью.

Обратите внимание, что это НЕ домашнее задание. Пример взят из слайдов лекций, где дано решение, но я не мог понять, как к нему добраться.

Источник

2 ответа

Решение

Поскольку вы не указали формат ввода, я предполагаю, что 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

В этом примере R0 = {00} и RF = {32}.

Осталось только определить переходное соотношение ω. Для этого объедините каждое правило перехода для A с каждым применимым правилом перехода для B. То есть объединить каждое правило перехода A (qi, σ) → (qj, γ) с каждым правилом B, которое имеет "γ" в качестве входного символа.

ω = {((qi, ph), σ) → ((qj, pk), δ): (qi, σ) → (qj, γ) ∈ α, 
                                     (ph, γ) → (pk, δ) ∈ β}

В примере это означает объединение (например) 0 1 a : b Т1 с 0 1 b : a а также 1 2 b : a Т2, чтобы получить:

00 11 а: а
01 12 а: а

Точно так же вы бы объединить 0 2 b : b Т1 с теми же 0 1 b : a а также 1 2 b : a Т2, 0 0 a : a Т1 с 1 1 a : d а также 1 2 a : c Т2 и с.

Обратите внимание, что у вас могут быть недоступные состояния (те, которые никогда не отображаются как "следующее" состояние) и переходы, которые никогда не произойдут (те из недоступных состояний). В качестве шага оптимизации вы можете удалить эти состояния и переходы. Однако, оставляя их, это не повлияет на правильность конструкции; это просто оптимизация.

Источник

Если вы более поддаются графическим объяснениям, следующий набор слайдов предоставляет на практике дополнительные графические примеры алгоритма компоновки, а также включает обсуждение эпсилон-переходов в компонентных преобразователях. Эпсилон-переходы усложняют процесс компоновки, и алгоритм, описанный в этом ответе, в этом случае может не дать правильного результата, в зависимости от используемого полукольца.

Смотрите слайды 10~35 для некоторых графических примеров:

http://www.gavo.t.u-tokyo.ac.jp/~novakj/wfst-algorithms.pdf

Источник

Т1 и Т2

Состав Т1 и Т2

Состояния композиции T представляют собой пары состояния T1 и состояния T2. T удовлетворяет следующим условиям:

  1. его начальное состояние - это пара начального состояния T1 и начального состояния T2
  2. Его конечные состояния - это пары конечного состояния T1 и конечного состояния T2.
  3. Существует переход t от (q1, q2) к (r1, r2) для каждой пары переходов T1 от q1 к r1 и T2 от q2 к r2, так что выходная метка T1 совпадает с входной меткой T2. Переход T берет свою входную метку из T1, свою выходную метку из T2, а его вес - это комбинация весов T1 и T2, выполненная с помощью той же операции, которая объединяет веса вдоль пути.

Поскольку весов нет, мы можем это игнорировать. Выше было взято именно из следующей красивой статьи. Ссылка здесь

Источник
Другие вопросы по тегам