主题：FST(Finite state transducer)
一、定义
1.简单介绍
FST本质上也是一种有限状态自动机FSA，区别是FST能够在两个符号集合中切换。下图是一个典型的FST。
A simple FST
图中的q0和q1分别代表两个不同的状态，arc上面的以：分割的符号分别代表了输入符号和输出符号。FST可以理解为这样一个机器，它读取一个string，同时生成一个string。还有其他的解读方式：
Four Explanations
2. 正式定义
Concepts
Q是N个状态的有限集合；Σ代表了输入符号的有限集合，Δ代表了输出符号的有限集合；q0代表了初始状态；F则是终止状态；q0和F都属于Q。
δ（q,w）代表了在当前状态为q时，接收到string w时将会转移到的所有可能状态的集合。σ（q,w）代表了在当前状态为q时，接收到string w时将会输出的可能string o的集合。
二、操作
FST包含了三种操作：
- union
- inverse: 简单地交换每条arc上面的输入和输出符号即可。
- composition: 组合，将两个transducer合为一个更高复杂的FST。比如一个从T1->T2的FST1和一个从T2->T3的FST2合并为一个从T1->T3的FST3，相当于对于T1施加FST1，之后继续施加FST2。
composition
FST composition
