有限状态转导器

边集有限不能由状态集有限推出：标签来自无限集 ${\mathrm{\Sigma }}^{\ast }\times {\mathrm{\Gamma }}^{\ast }$。如果允许无限多条字标签边，就能在两个状态之间直接放入任意关系的全部元素，有限状态约束便失去意义。有限性也保证每条边的输出长度存在统一最大值，线性输出界才有依据。

接受器只回答“这个字是否合格”，转导器还要留下一个结果。沿路径想象两卷纸带：输入卷轴按边标签被取走，输出卷轴按同一顺序不断接长。若每一步都消费输入，固定机器的输出长度至多随输入线性增长；一条边还能写出多个字符，所以输出长度不必等于输入长度。允许空输入边后，这个线性上界可能失效，必须另外检查静默环。

真正需要先分清的是“机器有几条运行”和“一个输入有几个输出”。非确定机器可以有多条成功路径；若这些路径全写出同一个字，关系仍是函数。反过来，只要两条成功路径给同一输入写出不同结果，语义便是多值关系。确定性、无歧义性与函数性因而是三个不同层次。

边上允许空输入会带来静默计算。有限状态不等于每个输入只有有限个输出：若某条成功运行经过环 $q\stackrel{\epsilon /z}{\to }q$，其中 $z\ne \epsilon$，则同一固定输入可沿该环绕行任意多次，得到形如 $u{z}^{k}v$（$k\ge 0$）的无限输出族；当环状态本身兼作初态和终态时，这才简化为 $z^k$。实际算法常把长输入标签正规化为一个字母或 $\epsilon$，并单独检查这类产出型空环。

设输入为十六进制字符，目标是输出便于朗读的符号名。一个确定转导器可在唯一状态 $q$ 上设置

把 $q$ 同时作为初态和终态，输入 A7F 的运行逐步产生 A-name、seven、foxtrot，最终输出 A-namesevenfoxtrot。输出没有隐含分隔符；若应用要求空格，空格必须明确写进相应边的输出字。

把原来的 A/A-name 边替换成两条读 A 的边，分别输出 a 与 ā，输入 A7 就对应 aseven 和 āseven 两个结果。这不是“机器随机选一个答案”的概率语义，而是关系中同时包含两对。

多条运行也可以给出同一结果：另构造初态 $q$、终态 $f$ 和不同中间状态 $r_1,r_2$，设置 $q\stackrel{A/a}{\to }{r}_i\stackrel{7/\mathtt{\text{seven}}}{\to }f$（$i=1,2$）。输入 A7 有两条不同的成功运行，输出却都为 aseven。两条路径通过不同状态区分，不能把边集合中完全相同的四元组重复写两次就算成两条边。

当输入字母表至少含两个可区分符号时，一向有限状态转导器不能实现任意长字的反转。读到前缀时若立即输出，未来字符会出现在错误一侧；若一直等待，又必须在有限状态中保存任意长前缀。单字母表上的反转就是恒等函数，不能充当这个不可实现性的见证；固定最大长度、允许读头回退或使用字符串寄存器也会越过上述论证的边界。类似地，边标签有限并不自动保证实时性：$\epsilon$ 输入环可能在不前进时持续输出。

有限状态转导器统一了字符转义、词形分析、拼写变体、协议字段改写和语音前端中的许多有限记忆转换。设计时应先写清语义是关系还是偏函数，再选择确定、非确定、双向或寄存器实现；否则“同一输入出现两条路径”很容易被误判成错误，或把真正的多值输出遗漏掉。

正规化可把每条长输入标签拆成逐字边，并用新状态串联；长输出标签可以保留为常量块，也能逐字符拆开。该变换改变状态和边的数量，不改变 $R_T$。进一步的组合、确定化和等价判定则依赖模型限制：接受器上熟悉的子集构造不能直接消除不同输出之间不断增长的延迟。

例如边 $p\stackrel{ab/xy}{\to }q$ 可拆为 $p\stackrel{a/x}{\to }r\stackrel{b/y}{\to }q$，其中 $r$ 是只服务这条边的新状态，且不是初态或终态。若把 $r$ 与其他边的中间状态随意合并，便可能拼出原图不存在的混合路径；增加专用中间状态正是保持关系不变的关键。

从图谱角度，本页只给共同接口。非确定有限状态转导器公理库非确定有限状态转导器Nondeterministic finite-state transducer · NFT · NFT transducer允许同一输入位置分叉出多条带输出运行，并以所有成功运行之输出集合定义关系的一向转导器。把关系语义正规化，Mealy 与 Moore 机器固定每步输出时机，sequential 与 subsequential 模型要求输入确定，而双向和流式模型改变了可利用的信息范围。它们共享有限控制，却没有共享同一表达能力或同一判定边界。