主题：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