双向有限状态转导器

一向转导器读过字符后只能靠有限状态记住它；2DFT 则可回到输入本身，把只读输入当作不会被修改的外部记忆。它没有栈或工作带，仍不能写输入格，但可以多次扫描以重排输出顺序。

双向移动不意味着任意长计算。对固定输入长度 $n$，确定机只有 $|Q|(n+2)$ 个配置；一条停机运行不能重复配置，所以步数至多线性于 $n$，输出长度也受每步最大输出块乘以该界控制。若重复配置，机器不会在“多绕几圈后”自行离开。

端标记承担算法阶段切换：先向右寻找末端，再向左输出，最后在左端停机。若定义省略端标记或成功位置，空字、越界移动和最后一块输出都会含混，两个表面相同的状态图可能定义不同偏函数。

反转函数 $f(w)=w^R$ 有一个简单 2DFT。机器从 $⊢$ 向右扫描到 $⊣$，这一阶段输出 $\epsilon$；看到右端标记后转入回扫状态，逐格左移，并在读取字符时输出该字符；再次看到 $⊢$ 后成功停机。

输入 abc 的位置—输出轨迹为

且前三步均无输出。回扫时依次读 c、b、a，累计输出 c、cb、cba，最后在左端停机。空字直接从右端转回左端，输出 $\epsilon$。

当字母表至少含两个符号时，一般一向函数型转导器不能实现无界反转，因为它既不能撤销已输出前缀，也不能保存整个输入；双向读头恰好跨过这条边界。单字母表上反转退化为恒等函数。可是 2DFT 仍不能输出 $w$ 共 $|w|$ 次：该结果长度为 $n^2$，超过固定 2DFT 停机运行的线性配置界。

若允许非确定双向运行并收集所有输出，语义会变成关系，函数性与等价问题随之改变。若允许可写工作带，则可以存储计数并反复扫描，已经不再是有限状态转导器。

双向读头自然表达“先检查后输出”“从末尾向前输出”以及依赖有限正则前后文的局部重写。每个输出字符仍由某次访问输入位置产生，这为 origin semantics 提供了清楚来源：输出不仅有值，还能标记来自哪个输入格。

Engelfriet–Hoogeboom 的刻画把确定 2DFT 与 MSO 可定义字符串传导连接起来；Alur–Černý 又以 copyless streaming string transducer 给出单向寄存器实现。三种模型的操作外观差异很大，却在上述精确约定下定义同一个 regular function 类。

等价并不承诺表示大小温和。把多次回扫编译成单遍寄存器更新时，需要编码 crossing sequences；反向模拟则要把寄存器中各片段未来的输出顺序变成有限控制。构造可有效完成，但状态数可能指数增长，工程上通常保留最贴近原算法的表示。