如何执行FST (有限状态转换器)合成

Question

请考虑以下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 o T2)我看到了一些算法，但理解不了太多。如果有人能用一种简单的方式解释它，那将是一个很大的帮助。

请注意，这不是家庭作业。这个例子取自讲课幻灯片，在幻灯片中给出了解决方案，但我不知道如何找到它。

Answer 1

如果您更愿意接受图形化解释，下面的幻灯片集提供了实践中合成算法的增量图形化示例，还包括对组件传感器中epsilon转换的讨论。Epsilon转换会使合成过程复杂化，在这种情况下，outis答案中描述的算法可能不会生成正确的结果，这取决于所使用的半环。

有关一些图形示例，请参阅幻灯片10至35：

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

Answer 2

T1和T2

​

T1与T2的组合

​

组合物T的状态是T1状态和T2状态的对。T满足以下条件：

它的初始状态是T1的初始状态和T2 的初始状态的对，它的最终状态是T1的最终状态和T2的最终状态的对。对于每一对从q1到r1的转换和从T2到的转换，存在从(q1，q2)到(r1，r2)的转换t，使得的输出标签匹配的输入标签。转换T从T1获取其输入标签，从T2获取其输出标签，其权重是T1和T2的权重的组合，其操作与沿着路径组合权重的操作相同。

因为没有权重，所以我们可以忽略它。上面是从下面一篇漂亮的论文中摘录出来的。Link here