有理关系

正则语言描述一卷纸带上允许出现哪些字；有理关系描述两卷纸带可以怎样不同步地对齐。一个输入字符可能对应多个输出字符，也可能被删除；输出还可在不消费输入时插入。有限控制只记对齐过程所需的有限上下文。

异步性是表达力的来源，也是闭包性质与普通正则语言不同的原因。把 $(a,b)$ 强行编码成等长的“字符对”只覆盖同步关系；删除、插入或变长替换会要求填充符，而不受约束的填充同步可能改变关系。

有理关系不是“可由任意程序计算的关系”的同义词。它的见证是有限图中的一条路径，因而局部步骤有限可列；需要比较两个无界远距离计数的关系通常超出该类，即使成员资格本身可判定。

对给定的一对具体字 $(x,y)$，成员资格仍可通过有限搜索决定：配置记录控制状态、已消费的输入位置和已匹配的输出位置，边只在两个标签与相应剩余片段吻合时推进。即使图有空环，可达性也只需记有限个位置对。这种局部可判定性与“两台机器是否对所有输入输出完全相同”的全局不可判定性并不冲突。

“输出输入字的任意子序列”是有理关系。转导器每读一个字符 $a$，非确定地选择 $a/a$（保留）或 $a/\epsilon$（删除）。对输入 aba，八条选择轨迹给出的输出集合去重后为

两个不同位置各自保留一个 a 会产生同一输出 a，再次说明关系不记录路径重数。这个例子也展示了语言运算公理库语言运算Language operations通过集合组合、字的连接、有限重复与编码映射，从已有语言构造新语言。中的删除型同态如何作为转导器边的局部选择出现。

逆关系 $R^{-1}$ 只需交换每条边的输入、输出标签，故仍有理；对上例，a 的逆像包含任意在删除后剩下一个 a 的字，若输入字母表固定仍可由有限转导器描述。有理关系还对并、关系复合、串接和星封闭。

边界例子是

更直接的反证利用有理转导保持正则语言的像为正则语言：若 $S$ 有理，则正则输入语言 $a^{\ast }$ 的像应是 $\{b^n{c}^n:n\ge 0\}$，但后者不正则。运行层面看，机器若边读 a 边输出 b，还需在结束后记住同一个无界 $n$ 再输出 $c^n$；若延迟全部输出，又要保存 $n$。另一个常见误区是认为有理关系对交封闭；一般两条异步对齐的交无法由有限控制同步复原。

Nivat 定理给出重要结构刻画：存在有限辅助字母表 $\mathrm{\Delta }$、正则语言 $L\subseteq {\mathrm{\Delta }}^{\ast }$ 与两个字母同态 $h:{\mathrm{\Delta }}^{\ast }\to {\mathrm{\Sigma }}^{\ast }$、$g:{\mathrm{\Delta }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$，使有理关系写成

其中每个辅助字母在每个坐标上只映成一个字母或 $\epsilon$，并可约定不在两个坐标上同时映成 $\epsilon$。这把“路径选择”集中到同一编码字 $u$，也精确解释了删除、插入、逆与复合为何仍受正则路径控制。

有理关系适合形态分析、发音词典、拼写候选和格式容错：应用本来就希望保留多个解释。若下游接口要求确定输出，必须额外证明关系单值或指定选择策略；单纯把图确定化通常会遇到不可消去的输出延迟。

判定边界比正则语言尖锐。给定一般非确定转导器，关系等价与包含不可判定；限制为函数型、有限值或确定模型后才恢复不同程度的可判定性。使用“都是有限状态”来推断所有经典 DFA 算法仍适用，是该主题最危险的类比。

纤维大小还形成有用的中间层：若每个输入至多有固定 $k$ 个输出，称为有限值或 $k$-值转导。它比函数型更宽、比任意关系更窄，某些等价问题因此恢复可判定；这里的 $k$ 必须对全部输入统一有界，而不是每个单独输入碰巧只有有限结果。