转导器复合

复合的难点是两台机器没有共同节拍。第一台一条边可能输出一串字，第二台可能用多步消费；第一台也可能暂时输出空字。构造必须保留所有合法交错，同时确保中间字完整匹配，而不是简单把“第 $i$ 条边”配给“第 $i$ 条边”。

对同步确定 Mealy 机，节拍恰好对齐，状态对就够了。对一般 NFT，先把中间带标签拆成单字母或 $\epsilon$：第一台产出 $b$ 的步与第二台消费 $b$ 的步同步；第一台产出 $\epsilon$ 或第二台消费 $\epsilon$ 时，只推进相应一侧。这样以有限状态对枚举所有合法交错，不需要保存无界中间队列；若要避免同一对齐被多种空步次序重复表示，可再加有限的 $\epsilon$-filter。

终止时机同样参与复合。第一台的终态输出必须先送入第二台，第二台确认中间输入结束后才可追加自己的终态输出。若在第一台刚到终态时就直接采用第二台当前终态，而没有消费最后输出块，会漏掉或增加结果。

构造出的复合机可能比语义更有歧义。同一个中间字 $y$ 可以由第一台多条路径产生，第二台也可能有多条路径消费它；这些路径组合都会出现，但关系语义最终只保留 $(x,z)$。因此“两个函数复合后仍是函数”是语义闭包，不保证机械构造得到的 NFT 每个输入只有一条成功运行。

令 $T_1$ 做简化实体转义：普通 a,b 原样输出，& 输出 &。令 $T_2$ 把 ASCII 字母改成大写，并原样保留 & 与 ;。两者都只有一个终态，初始和终态输出为空。

输入 a&b 经第一台的三步为

第二台再逐字符读取中间字，依次输出 A、&、A、M、P、;、B，故复合结果为 A&B。若颠倒顺序，先大写再转义得到 A&B，说明函数复合通常不可交换。

若第二台不认识分号，则 $T_1$ 虽对输入有定义，复合偏函数仍在含 & 的输入上未定义。若第一台对 & 有两个输出 & 与 and，关系复合会保留第二台可消费的所有中间见证，不可任意选一条。

状态规模是另一条边界。Mealy 复合至多先产生 $|Q_1||Q_2|$ 个状态；一般一向 NFT 在按显式标签长度拆边后，核心仍是状态积和常数规模的空步过滤，所以单次构造对展开后的两份表示是多项式的。指数膨胀主要出现在多级流水线反复取状态积，或把双向扫描、SST 变量流翻译到另一种表示时。闭包只保证存在有限结果，不保证长流水线的最终机器仍小。

复合让复杂转换保持模块化：先词法规范化，再字段重写，最后编码输出；每层可以单独测试，然后用端到端等价检查验证优化后的合成机。确定模型中，删除不可达积状态和惰性生成能显著减小实际图。

有理关系形成以字母表自由幺半群为对象、以转导为箭头的组合结构，恒等关系由逐字复制转导器实现，关系复合满足结合律。因此多级流水线括号如何放不改变语义，但会影响中间表示大小和构造成本。

在 regular function 世界，复合可借 MSO 解释封闭性证明，也可在 2DFT 或 copyless SST 上构造。实践中应避免来回翻译模型：选择最能保留局部结构的一种表示，并在真正出现状态爆炸时才引入惰性或符号化，而不是预先建立复杂框架。

若流水线只执行一次，直接串行运行两台确定机器往往比物化复合状态图更省空间；只有需要反复查询、最小化或对整体做等价检查时，预先合成才可能回本。这个工程取舍不改变闭包定理，却决定状态爆炸是在编译阶段还是运行阶段承担。