非确定性自动机可以很容易地对输入字符串的只是保持状态自动机中的曲目，并有多远输入字符串时，它已经得到了模拟。 但如何才能具有不确定性的换能器（换能器，当然也可以输入符号转化为输出的符号，并给作为输出字符串，而不仅仅是一个布尔值）来模拟？ 看来，这是比较复杂的，因为我们需要跟踪，不知何故，输出字符串，可能由于非确定性是众多的。
Answer 1:
首先，一些理论。 下面是不同的代数结构：
发生器（过渡系统）
受体（自动）
换能器（机）
括号内的术语相当普遍在文献中找到，可惜他们被错误的使用往往不是。 这些代数结构彼此类似众所周知的了，并且可以从一个到另一个或杂合体通过众多的小变化时导通。 但是，这不应该是他们AR根本不同的事实分心：
发电机是一种语言的一个建设性的表示，即，一组的（有限的或无限的）字。 你不确定性遍历发电机，这样做你产生这种语言的所有单词。
受体再次是用于定义一组单词（语言）构建体，但每个均代表对所有可能的单词（有限或无限）的指示器的功能 。 因此，他们的每个单词映射到布尔值（其可以被适当地延伸到有限或无限输出字，以试图与换能器来比较 - 有虽然区分代数差）。
的换能器表示的函数的每个容许的有限输入字映射到有限的输出字 。
在有限语言的上下文中，受体和换能器之间的区别变得不那么显着，因为受体可以接受或不能任何有限字，而不论它的长度，从而它产生对于每个这样的单词的输出字。 通过从受体布尔输出的连环，可以创建用于每个有限的输入字（即，通过从给定的输入字的每个前缀catenating的输出）的有限输出字。 这种试图弥合这两个概念，虽然在机理上是正确的，但是扭曲所涉及的概念。
在无限的字语言的背景下，这种区别更加清晰。 一个无限的字自动机 不能针对给定的（无限）的输入字的有限前缀产生输出。 此限制是在整个（无限）字被定义无限字接受的结果。 其结果是，受体如果这样的观点出发，优选每一个输入单词映射到布尔值，或者输出字。 与此相反，换能器（机器）映射任何输入字的每个有限前缀，以相等的长度的有限输出字。 出于这个原因，他们被称为连续的机器，因为他们的反应一步一步。
有两种不同类型的传感器：
- 米利机
- 摩尔机
甲摩尔机可以由米利机来表示。 并不是每一个米利型机是由摩尔机表示的。 文献通常是在界定和比较这两种类型的传感器错误，请参考原文出版物的正确定义。
所以这两个定义是确定性的。 没有此限制决定的理由：换能器是用来控制系统，所以我们想知道确定性申请下一控制动作应该是什么。 这导致了确定性的传感器成为文学的标准。
然而，非确定性的传感器也可以是有用的，例如作为多种策略简洁表示。 然而，它们在被执行时是有意义的仅遵循一条路径，并产生一个输出字，而不是多个同时（如为在其执行期间产生了非确定性受体的副本的情况下）。
因此它变得清晰，换能器的非确定性模拟不符合它的预期用途。 它代表一组替代的策略（即，也可以混合，如果不以固定的方式，每个单个播放期间determinize）。
所以，你确实需要创建的迅速炸毁可能的输出字的（不断扩大的）树。 这棵树是本质上，你会通过剥离其输入注释的传感器获得的发电机（转换系统）展开。
Answer 2:
基本上你做相同的NFA但这次不是返回真或假，你的输出添加到输出集合。 这是一个有点伪代码：
function rec(in, current_state, pos, out)
if(current_state.isFinal && pos == in.length) out_set += out
for(t <- lambda transition going out from current_state)
rec(in, t.destination, pos, out + t.output_symbol)
for(t <- transition going out from current_state for symbol in(pos)
rec(in, t.destination, pos+1, out + t.output_symbol)
文章来源: How can one simulate nondeterministic finite transducers?
