有理关系

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

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

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

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

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

两个不同位置各自保留一个 a 会产生同一输出 a，再次说明关系不记录路径重数。若把“保留 $a$”与“删除 $a$”编码为两个不同的路径字母，输出投影才是语言运算理路语言运算Language operations通过集合组合、字的连接、有限重复与编码映射，从已有语言构造新语言。中的删除型同态；它不是在原字母表上规定同一个 $a$ 有时保留、有时删除的一元函数。

固定输入也可能有无限多输出。例如一个初态同时为终态，仅有 $\epsilon /b$ 自环，就实现 $\{(\epsilon ,b^n):n\ge 0\}$。对给定字对 $(\epsilon ,b^3)$，只需三次输出匹配即可确认成员资格；“输出集合无限”不等于一个有限候选字对无法验证。对长度 $m,n$ 的候选输入输出，状态—位置配置至多 $|Q|(m+1)(n+1)$ 个，标记访问过的配置即可避免空环导致搜索不终止。

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

边界例子是

更直接的反证利用有理转导保持正则语言的像为正则语言：若 $S$ 有理，则正则输入语言 $a^{\ast }$ 的像应是 $\{b^n{c}^n:n\ge 0\}$，但后者由正则泵引理理路正则语言泵引理Pumping lemma for regular languages足够长的正则语言成员必有一段位于短前缀中的非空环，可删除或重复任意多次而仍留在语言中。可知不正则。运行层面看，机器若边读 a 边输出 b，还需在结束后记住同一个无界 $n$ 再输出 $c^n$；若延迟全部输出，又要保存 $n$。另一个常见误区是认为有理关系对交封闭；一般两条异步对齐的交无法由有限控制同步复原。

上述正则像性质可从机器直接看出：先让转导器的输入控制与一个识别输入限制的 DFA 同步，随后忘掉输入标签，只保留输出字标签；把长输出边拆开，并用新初态、新终态处理有限边界输出，就得到ε-NFA理路ε-NFAEpsilon-NFA · NFA with epsilon transitions允许沿不消耗输入的 ε-边改变控制状态、便于组合局部自动机的 NFA。。它的语言恰是所选正则输入的全部输出，因此仍正则。空输出变成 ε-边，并不从值域中删去空字。

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$ 必须对全部输入统一有界，而不是每个单独输入碰巧只有有限结果。