Sequential 转导器

Sequential 机器是一位不能回头、不能撤销已写内容的抄写员。状态记录有限上下文，当前输入决定下一状态和此刻追加的字符串。它可以暂缓有限信息，却不能把任意长前缀压在心里等待最后一个字符。

输入确定不要求输出长度同步。一条边可以输出空字、一个字符或固定长短语；例如字符转义可以把 & 写成五字符实体。真正受限的是已输出前缀不可修改，以及有限状态只能维持有界种类的延迟。

因此，机器读完前缀 $u$ 时已经写出的内容，必须是每个可接受续接 $uv$ 的最终输出的公共前缀。机器可以少写并把有限残余放进状态，却不能预写一个将来可能被推翻的字符。这个前缀单调性是分析某个转换能否在线实现的直接工具。

偏函数语义来自部分转移和终态集合。完整消费输入但落在非终态仍是未定义；路径中途缺边也是未定义。若删掉 $F$ 并默认所有状态终止，就改变了定义域，尤其会把本应等待闭合符号的前缀误当成完整输入。

构造一个 HTML 文本转义器，输入字母表简化为 a、b、&、<。机器只有一个状态 $q$，既是初态又是终态，并设置

输入 a&<b 的四步输出块依次为 a、&、<、b，连接后为 a&<b。实体中的分号是边输出的一部分，终止时不会再自动补字符。这个例子也说明输出可比输入长而无需额外状态。

在至少含两个符号的字母表上，反转 $w\mapsto w^R$ 不是 sequential 函数。对所有前缀都可能继续输入，机器在看到 a 时不知道它最终应处在输出末尾的哪个位置；先写会破坏顺序，等待则需保存无界的原前缀。单字母表上的反转等于恒等函数，固定最大长度的反转也能用足够多状态硬编码；两者都没有触及无界次序重排这一障碍。

另一个边界来自终态后缀。函数 $f(a^n)=a^{n-1}b$（$n\ge 1$）可以把最后的 b 留到输入结束，但 pure sequential 机器既不知道哪次 a 是最后一次，也没有终止输出接口；它将成为下一页严格包含关系的见证。

Sequential 函数对复合封闭。若第一台的一条边输出固定字 $u$，可以在构造时让第二台从当前状态完整跑过 $u$，把其输出块和终态合并进积状态。因为每条边的 $u$ 来自有限表，这一步不会需要无界缓冲。

输出推动把各状态之后所有可能输出的最长公共前缀尽量前移，可以得到便于比较和最小化的规范形式。随后按“相同剩余函数”合并状态，形成类似 Myhill–Nerode 的最小表示；仅按输入自动机语言最小化不足以保留输出。

Sequential 转导器适合字符转义、确定词法规范化和在线协议改写。若转换必须依据任意远的末尾选择早期输出，应该先检查 subsequential 可实现性或孪生性质，而不是不断为有限样例增加状态。

实现中还应区分“读取完当前缓冲区”与“输入流真正结束”。只有后者才能触发终止判定；若网络分片暂时为空就把当前状态当终态，会把同一个逻辑输入切成多个函数调用，改变定义域与输出边界。