computer-science - 如何模拟不确定的有限换能器？

Question

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

Answer 1

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


发电机（过渡系统）
受体（自动机）
换能器（机器）


括号内的术语在文献中很常见，可惜它们经常被错误地使用。这些代数结构彼此之间非常相似，并且可以通过大量的小变化从一个转换为另一个或混合。但是，这不应该从它们根本不同的事实中分散注意力：


生成器是一种语言的建设性表示形式，即一组（有限或无限）单词。您不确定地遍历生成器，并以此来生成该语言中的所有单词。
接受者还是用于定义一组单词（语言）的构造，但是每个接受者都代表所有可能单词（有限或无限）的指示符功能。因此，他们将每个单词映射到一个布尔值（可以适当地扩展到一个有限或无限的输出单词，以尝试与换能器进行比较-尽管存在明显的代数差异）。
换能器代表将每个允许的有限输入字映射到有限输出字的功能。


在有限语言的上下文中，接受者和换能器之间的区别变得不太明显，因为接受者可以接受或不接受任何有限词，而不论其长度如何，因此它为每个这样的词产生一个输出词。通过对来自接收器的布尔输出进行分类，可以为每个有限输入字创建一个有限输出字（即，通过给定输入字的每个前缀连接输出）。尽管在机械上是正确的，但这种尝试弥合了这两个概念的尝试仍然扭曲了所涉及的概念。

在无限词语言的上下文中，区别更加明显。 infinite-word automaton无法为给定（无限）输入单词的有限前缀生成输出。这种限制是在整个（无限）单词上定义无限单词接受的结果。结果，接受者将每个输入字映射到布尔值，或者如果首选这样的观点，则将输出字映射到布尔值。相反，换能器（机器）将任何输入字的每个有限前缀映射到相等长度的有限输出字。因此，它们被称为顺序机器，因为它们会逐步反应。

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


Mealy machines
Moore machines


Moore机器可以用Mealy机器表示。并非每台Mealy机器都可以由Moore机器代表。在定义和比较这两种类型的换能器方面，文献通常是错误的，请参考原始出版物以获取正确的定义。

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

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

因此，很明显，换能器的不确定性仿真不符合其预期用途。它代表了一组可供选择的策略（如果在每个单打游戏中都不以固定方式确定，也可以混合使用）。

因此，实际上您必须创建一个（可能不断扩展的）可能的输出单词树，并且很快就会崩溃。本质上，这棵树是生成器（转换系统）的展开，您可以通过将其输入注释的换能器剥离而得到。