如何模拟非确定性有限换能器？

Question

只需跟踪自动机所处的状态，以及自动机在输入字符串中的距离，就可以很容易地在输入字符串上模拟非确定自动机。但是如何模拟不确定的换能器(当然，换能器可以将输入符号转换为输出符号，并将字符串作为输出，而不仅仅是布尔值)？这似乎更复杂，因为我们需要以某种方式跟踪输出字符串，由于不确定性，输出字符串可能会很多。

Answer 1

首先，一些理论。以下是不同的代数结构：

• 生成器(转换系统)

自动机接受器(

• acceptors (

))

• transducers (machines)

(高级传感器(机器))

带括号的术语在文献中很常见，可惜它们经常被错误地使用。众所周知，这些代数结构彼此非常相似，并且可以通过许多小的变化从一个转变为另一个或混合。但这不应该分散注意力，因为它们从根本上是不同的：

• 生成器是一种语言的构造性表示，即一组(有限或无限)单词。您不确定地遍历生成器，并在此过程中生成该语言中的所有单词。

• 接受器也是用于定义一组单词(语言)的构造，但每个接受器表示所有可能的单词(有限或无限)的指示器函数。因此，它们将每个字映射到布尔值(可以适当地扩展到有限或无限输出字，以尝试与换能器进行比较-通过区分代数difference).

• a换能器表示将每个允许的有限输入字映射到有限输出字的函数。

在有限语言的上下文中，接受者和转导者之间的区别变得不那么明显，因为接受者可以接受或不接受任何有限的单词，而不管其长度如何，因此它为每个这样的单词产生一个输出单词。通过连接来自接受者的布尔输出，可以为每个有限输入字创建有限输出字(即，通过连接来自给定输入字的每个前缀的输出)。这种试图在两个概念之间架起桥梁的尝试，尽管从机械上讲是正确的，但却扭曲了相关的概念。

在无限单词语言的上下文中，区别更加明显。infinite-word automaton不能为给定(无限)输入字的有限前缀产生输出。此限制是在整个(无限)单词上定义无限单词接受的结果。因此，接受者将每个输入单词映射到布尔值，或者输出单词(如果这种观点是首选的话)。相反，传感器(机器)将任何输入字的每个有限前缀映射到相同长度的有限输出字。因此，它们被称为顺序机器，因为它们是一步一步地做出反应。

有两种不同类型的传感器：

• Mealy machines
• Moore machines

Moore机器可以用Mealy机器来表示。并不是每台Mealy机器都可以用Moore机器来表示。文献在定义和比较这两种类型的传感器时通常是错误的，请参考原始出版物以获得正确的定义。

所以这两种定义都是确定性的。这种确定性的限制是有原因的:传感器是用来控制系统的，所以我们想要确定性地知道下一个要应用的控制动作应该是什么。这导致确定性换能器成为文献中的标准。

然而，非确定性换能器也可以是有用的，例如，作为多个策略的紧凑表示。然而，当它们被执行时，只遵循一条路径并产生单个输出字是有意义的，而不是同时产生多个输出字(就像在执行过程中产生的非确定性接受器的副本的情况一样)。

因此，很明显，换能器的非确定性模拟并不对应于其预期用途。它代表了一组可供选择的策略(如果在每个单独的游戏中没有以固定的方式确定，也可以混合)。

因此，实际上，您必须创建一个(不断扩展的)树，其中包含快速爆炸的可能输出单词。该树本质上是生成器(转换系统)的展开，您可以通过剥离传感器的输入注释来获得生成器(转换系统)。

Answer 2

基本上与对NFA执行相同的操作，但这次不是返回true或false，而是将输出添加到输出集中。下面是一些伪代码：

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)