Subsequential 转导器

终态输出相当于一个有限的“收尾信封”。机器扫描时仍只能保留有限状态，但看到输入确实结束后，可以按最终状态补上一个预先存好的短语。这足以处理“最后一个字符如何改写”或“合法结束时追加闭合标记”等任务。

信封大小由有限转导器固定，不能随输入长度增长。Subsequential 比 pure sequential 强，却仍不能把整个任意长输入缓存在终态；若所需收尾长度无界，就必须在扫描过程中逐步产生，或换用寄存器、双向读头等模型。

具体地，令 $B=\underset{q\in F}{max}|\rho (q)|$。无论输入多长，机器在读头到达末端后至多再写 $B$ 个字符；所有更长的信息必须已经沿输入边输出。这个统一常数给出了检验“能否全留到最后”的直接上界。

有些资料把带终态输出的模型也简称 sequential。为避免术语漂移，本批固定 pure sequential / subsequential 这组区分；阅读定理时应先看作者是否含终态函数，而不能只看英文名。

定义 $f(a^n)=a^{n-1}b$，定义域为 $a^{+}$。取初态 $q_0$ 非终止，第一次读 a 时输出 $\epsilon$ 并进入终态 $q_1$；在 $q_1$ 每再读一个 a 就输出一个 a，最后设置 $\rho (q_1)=b$。

输入 aaaa 的轨迹是

边输出连接为 aaa，输入结束后再写终态输出 b，结果为 aaab。空字停在非终态，所以函数未定义；a 则没有边输出，只由终态写出 b。

为什么 pure sequential 做不到？若它在某次 a 上写出最终的 b，同一输入还可能继续一个 a，这个 b 就过早；若始终只写 a，结束时又无接口改写最后一个位置。有限状态无法预知哪一位置是末尾。终态输出恰好补上这一位，但不能实现 $a^n\mapsto b^n{a}^n$ 之类需要长度随 $n$ 增长的收尾。

终态输出还会影响等价测试：两台机器在所有转移上输出相同，若某个共同可达终态的 $\rho$ 不同，仍不等价。把终态当普通接受标记会漏掉最短反例，尤其是空字。

Subsequential 函数对复合封闭，也存在输出推动与最小化理论。规范化时要把能够安全前移的公共前缀从后继和终态输出中抽出；完成推动后，再按剩余函数商掉等价状态，最小机在适当约定下唯一到同构。

并非每个函数型有理传导都 subsequential。判据不是“测试样例上看起来确定”，而是任意同步分支的输出延迟能否在循环中保持一致；Choffrut 的孪生性质给出必要充分条件和有效确定化方法。

词典查找、词形生成、数字格式化和只在合法结束时补标记的流式任务常自然落在本类。若定义域不是前缀封闭，终态集合负责区分“当前前缀已有输出”与“完整输入真正有效”，这在增量接口中尤其重要。