2

我只是自动机领域的新手。看了很多文章，看了很多视频。我坚持了一些最初的话题。对其他人来说可能很容易。但是花了很多时间之后，我仍然无法理解它。主题是：字母表中的歧义

一个字母是 = {A, Aa, bab, d}，一个字符串是 s= AababA

并且作者说，这是模棱两可的字母，因为当计算机读取它时，它是从左到右读取的。在大写A之后，再有A是小a的前缀，会产生歧义。字母（符号）不应再次作为新字母的前缀。而且作者说。我们将以两种方式对其进行标记（AababA）：

  • (Aa) (Bab) (A)
  • (A) (阿巴) (A)

之后，第一个可以，第二个不可以，因为上面定义的字母不明确。

  1. 以两种方式标记上述字符串的过程是什么？有什么具体规则吗？
  2. 由于第二组，字母表如何模棱两可。
  3. 如果由于A的前缀而无效，那怎么办？前缀在字母歧义中的作用是什么？
  4. 如果我们不考虑前缀，只是简单地将两个字符串组与上面的字母匹配，那么我们可以很容易地判断，第二个不匹配上面的字母，那么为什么我们需要讨论那个前缀呢？

我希望，这个问题会被认为是重要的，所以这个答案将帮助我摆脱这种困惑。我将非常感激。

4

1 回答 1

0

作者选择了一个令人困惑的例子。如果您分享获得此示例的来源，我可以给出更好的答案，但我认为在这种情况下，没有实际的歧义。如果您看到Aa，您可以知道第一个词位必须是“Aa”，因为字母表中没有任何内容以“a”开头。

举个更简单的例子，考虑字母 {A, a, Aa} 和字符串“AaaAaaA”

您可以通过以下方式对其进行标记：

(A) (A) (a) (A) (a) (a) (A)
(A) (Aa) (A) (a) (a) (A)
(A) (A) (a) (Aa) (a) (A)
(A) (Aa) (Aa) (A)

这通常通过选择在每种情况下匹配的最长词位来解决，这将产生最后的标记化。

现在让我们回到您的示例，但让我们使字符串有点不同：“AababAe”。

您可以通过以下方式标记字符串：

(Aa) (bab) (A) <error>
(A) <error>

在一个分支中，您有一个错误。在一个分支中，你没有。正如您所指出的，标记器应该选择第一个。不过，两者都有错误。关键是这里有一个明确的选择来选择最长的有效标记化。字母表中的任何内容都不会迫使您做出此选择。选择最短匹配选项同样有效。这将是非常不切实际的，但它是一个有效的选择。

于 2018-09-12T12:23:02.057 回答