4

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

4

2 回答 2

3

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

  • 发电机（过渡系统）

  • 接受者（自动机）

  • 传感器（机器）

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

  • 生成器是一种语言的建设性表示，即一组（有限或无限）单词。您不确定地遍历生成器，并在这样做时生成该语言的所有单词。

  • 接受器同样是用于定义一组单词（语言）的构造，但每个都代表所有可能单词（有限或无限）的指示函数。因此，他们将每个单词映射到一个布尔值（可以适当地将其扩展到有限或无限的输出单词，以尝试与传感器进行比较——尽管存在明显的代数差异）。

  • 一个转换器表示一个函数，将每个可接受的有限输入字映射到一个有限输出字。

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

在无限字语言的上下文中，区别更加清晰。无限字自动机 不能为给定（无限）输入字的有限前缀产生输出。这种限制是在整个（无限）词上定义无限词接受的结果。因此，接受者将每个输入词映射到一个布尔值，或者如果这种观点是首选的，则输出词。相反，转换器（机器）将任何输入字的每个有限前缀映射到等长的有限输出字。出于这个原因，它们被称为顺序机，因为它们是逐步反应的。

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

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

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

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

因此很明显，换能器的非确定性模拟不符合其预期用途。它代表了一组替代策略（如果在每场比赛中没有以固定方式确定，也可以混合使用）。

因此，您确实必须创建一个（不断扩展的）可能输出单词的树，这些单词会迅速爆炸。这棵树本质上是生成器（转换系统）的展开，您可以通过剥离传感器的输入注释来获得。

于 2014-07-25T08:05:01.980 回答
0

基本上，您对 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)
于 2012-07-14T20:06:44.903 回答