如何进行FST(有限状态换能器)合成 [英] How to perform FST (Finite State Transducer) composition

问题描述

请考虑以下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)上执行合成操作 我看到了一些算法，但不太了解.如果有人可以轻松地解释它，那将是一个很大的帮助.

How do I perform the composition operation on these two FSTs (i.e. T1 o T2) I saw some algorithms but couldn't understand much. If anyone could explain it in a easy way it would be a major help.

请注意，这不是家庭作业.该示例取自提供解决方案的讲义幻灯片，但我不知道如何解决.

Please note that this is NOT a homework. The example is taken from the lecture slides where the solution is given but I couldn't figure out how to get to it.

推荐答案

由于您未指定输入格式，因此我假设0为初始状态，所有出现在第二列而不是第一列的整数接受状态(T1为3，T2为2)，每一行都是过渡关系的元素，给出前一个状态，下一个状态，输入字母和输出字母.

Since you didn't specify the input format, I'm assuming that 0 is the initial state, any integers that appear in the second column but not the first are accepting states (3 for T1 and 2 for T2), and each row is an element of the transition relation, giving the the previous state, the next state, the input letter and the output letter.

任何对FST的操作都需要产生一个新的FST，因此我们需要状态，输入字母，输出字母，初始状态，最终状态和过渡关系(下面给出了FST A，B和W的规格按此顺序).假设我们的FST是:

Any operation on FSTs needs to produce a new FST, so we need states, an input alphabet, an output alphabet, initial states, final states and a transition relation (the specifications of the FSTs A, B and W below are given in this order). Suppose our FSTs are:

A = (Q, Σ, Γ, Q0, QF, α)
B = (P, Γ, Δ, P0, PF, β)

我们想找到

W = (R, Σ, Δ, R0, RF, ω) = A ∘ B

请注意，我们不需要确定W的字母；成分的定义可以做到这一点.

Note that we don't need to determine the alphabets of W; the definition of composition does that.

想象一下，将A和B串联运行，将A的输出磁带作为B的输入磁带进行馈送.组合FST的状态只是A和B的组合状态.换句话说，组合物的状态在各个FST的状态的叉积中.

Imagine running A and B in series, with A's output tape fed as B's input tape. The state of the combined FST is simply the combined states of A and B. In other words, the states of the composition are in the cross product of the states of the individual FSTs.

R = Q × P

在您的示例中，W的状态为整数对:

In your example, the states of W would be pairs of integers:

R = {(0,0), (0,1), ... (3, 2)}

尽管我们可以重新编号并获得(例如):

though we could renumber these and get (for example):

R = {00, 01, 02, 10, 11, 12, 20, 21, 22, 30, 31, 32}

类似地，组成的FST的初始状态和接受状态是组件FST中的状态的叉积.特别是，R接受字符串 iff A和B都接受该字符串.

Similarly, initial and accepting states of the composed FST are the cross products of those in the component FSTs. In particular, R accepts a string iff A and B both accept the string.

R0 = Q0 × P0
RF = QF × PF

在示例中，R ₀ = {00}，R _F = {32}.

In the example, R₀ = {00} and R_F = {32}.

剩下的就是确定过渡关系ω.为此，将可能适用的A的每个转换规则与B的每个转换规则结合起来.即，将A (qi, σ) → (qj, γ)的每个转换规则与以γ"作为输入字符的B的每个规则结合起来.

All that remains is to determine the transition relationship ω. For this, combine each transition rule for A with every transition rule for B that might apply. That is, combine each transition rule of A (qi, σ) → (qj, γ) with every rule of B that has a "γ" as the input character.

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

在示例中，这意味着将(例如)T1的0 1 a : b与T2的0 1 b : a和1 2 b : a组合起来:

In the example, this means combining (e.g.) 0 1 a : b of T1 with 0 1 b : a and 1 2 b : a of T2 to get:

00 11 a : a
01 12 a : a

类似地，您将T1的0 2 b : b与T2的0 1 b : a和1 2 b : a，T1的0 0 a : a与T2& c的1 1 a : d和1 2 a : c组合在一起.

Similarly, you'd combine 0 2 b : b of T1 with those same 0 1 b : a and 1 2 b : a of T2, 0 0 a : a of T1 with 1 1 a : d and 1 2 a : c of T2 &c.

请注意，您可能会遇到无法到达的状态(那些永远不会显示为下一个"状态的状态)和永远不会发生的转换(来自不可到达状态的状态).作为优化步骤，您可以删除这些状态和过渡.但是，将它们留在里面不会影响结构的正确性.这只是一个优化.

Note that you might have unreachable states (those that never appear as a "next" state) and transitions that will never occur (those from unreachable states). As an optimization step, you can remove those states and transitions. However, leaving them in will not affect the correctness of the construction; it's simply an optimization.

这篇关于如何进行FST(有限状态换能器)合成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！