非确定有限状态转导器

NFT 像一台在每个位置保留若干候选分析的扫描器。候选分支共享同一输入，却可以选择不同切分、词形解释或输出拼写；只有最终到达终态的路径才贡献结果。语义收集的是所有成功输出，而不是挑选“最可能”或“第一条”路径。

非确定性解决的是有限描述中的选择，不提供无限记忆。机器可以猜测未来会出现什么，再用后续输入验证猜测；猜错的分支最终不接受。它因此能实现一些无法在线确定输出的有理函数，但若成功分支对同一输入留下不同输出，结果仍是关系而非函数。

$\epsilon$ 输入边特别适合连接组件，却会让执行器复杂。模拟时不能只维护状态集合，还要维护输出残差；能产出非空字且位于成功路径上的空环甚至使单个输入拥有无限输出。许多判定定理直接假设 real-time，即每条计算边恰读一个输入字母；此时每个固定输入只有有限多条运行。含空输入边的机器只有在相应定理允许的条件下才能先正规化：具有无限纤维的产出型空环不可能被保持关系地编译成 real-time NFT。

若存在统一常数 $k$，使每个输入的输出集合大小至多为 $k$，称机器为 $k$-值；$k=1$ 正是函数型。这个“值数”仍不限制成功路径数，因为许多路径可以汇到同一输出。有限值条件比无歧义弱，却足以改变若干等价判定的可解边界。

设输入字母表含 a,b，输出同样含 a,b。在唯一控制状态 $q$ 上，读 b 只能输出 b；读 a 有两条边，分别输出 a 与 aa。$q$ 同时是初态、终态，且初始、终态输出均为 $\epsilon$。

输入 ab 有两条成功轨迹

所以得到输出集合 $\{\mathtt{\text{ab}},\mathtt{\text{aab}}\}$。输入 aa 则有四条运行，输出字集合只有 aa、aaa、aaaa 三个元素，因为两种“一处加倍”的运行都产生 aaa。这清楚区分了歧义度与关系值数。

若再添加 $q\stackrel{\epsilon /x}{\to }q$，那么空输入就有 $x^k$（$k\ge 0$）这些输出；有限状态与有限边没有阻止关系的一个纤维无限。相反，禁止输入空边也不保证函数性，上述 a 的两条消费边已经足够产生两个结果。

NFT 仍是一向模型。它能猜测“最后会读到 b 还是 c”并沿途输出不同字，再由末字符验证；但它不能把已经消费的任意长前缀重新读取。允许双向读头或字符串寄存器会得到更大的函数类，不能借“非确定”二字把这些能力混入。

NFT 所实现的关系正是经典有理关系。并、串接与迭代可用不交并状态和 $\epsilon$ 接线构造；关系复合也保持在该类内。不过交、补和关系包含一般不享有接受器那样的闭包或可判定性。

函数性问题询问每个输入是否至多有一个输出，它不同于输入无歧义性。即使多条成功路径写出同一结果，机器仍然函数型；算法通常在同步平方构造中追踪两条运行的输出延迟，寻找最终无法抵消的差异。

实际形态分析器、拼写归一化器和语音词典常保留 NFT，因为不同解释本来就是所需输出。若应用需要单一答案，还必须证明函数性、加入明确优先规则，或在模型外评分；随意取遍历顺序中的第一条路径不会定义稳定的数学转导。

执行器若要枚举输出，还必须说明顺序、去重和终止策略。存在产生输出的空环时，完整枚举永不结束；即便每个纤维有限，重复路径也可能造成大量相同字。关系的数学定义隐藏了这些运行成本，API 不能隐藏。