5

w^R 是 w 的倒数， w 是 {0, 1}* 。所以 TM 需要判断一个词后跟这个词的反义词后跟这个词。我不想要答案，我只想要一个开始并走上正轨的线索。

4

3 回答 3

6

由于已经过了一段时间并且可能不再需要答案，我想我会提出一个解决方案，以帮助未来的学生寻找图灵机如何识别一种语言的示例。

这是想法。我们将带字母{0, 1, a, b, c, d}作为磁带字母表，并制作一个识别ww^R w的单磁带单无限磁带图灵机。该机器将分五个阶段工作：

  1. 将前缀 ww^R 中的 0 和 1 替换为 a 和 b。
  2. 看看 ww^R 是否是回文。
  3. 将磁带恢复到原始状态。
  4. 将后缀 w^R w 中的 0 和 1 替换为 c 和 d。
  5. 看看 w^R 是否是回文。

请注意，这只是表明存在识别这种语言的图灵机的一种简单（对我来说就是）方式。自然地，证明在任何图灵等效的计算系统中存在解决这个问题的算法同样好（它证明存在一个 TM）......不过，这概述了一个这样的 TM 的构造。另请注意，可能有更简单、更有效或更直观的 TM 来解决这个问题……同样，这只是一种方法。

第 1 步将按如下方式进行：

  • 前提条件：磁带以一个空格开头，包含 (0+1)* 中的任意字符串，后面跟着一个无限长的空格字符串。

  • 后置条件：如果磁带为空或长度不是 3 的倍数，则停止；否则，磁带以空格开头，后面是 (a+b)^2n (c+d)^n，然后是无限的空格字符串。

    1. 向右移动。
    2. 如果为空，则停止接受。否则，向右扫描直到找到一个空的磁带方块，然后向左移动。
    3. 如果为 0，则将磁带更改为 c，如果为 1，则更改为 d。
    4. 向左扫描，直到找到一个空的磁带方块。向右移。
    5. 如果磁带是 0 或 1，则更改为 a 或 b，然后向右移动。如果磁带是 c 或 d，则停止拒绝。
    6. 如果磁带是 0 或 1，则更改为 a 或 b，然后向右移动。如果磁带是 c 或 d，则停止拒绝。
    7. 如果磁带是 c 或 d，则扫描到磁带的开头并转到步骤 2。否则，向右扫描直到 c 或 d，然后向左移动。
    8. 如果为 0，则将磁带更改为 c，如果为 1，则更改为 d。
    9. 向左扫描，直到找到 a 或 b。向右移。
    10. 从 4 开始重复。

第 2 步将按如下方式进行：

  • 前提条件：磁带以一个空格开头，后面是 (a+b)^2n (c+d)^n，后面是无限长的空格字符串。

  • 后置条件：如果前缀 (a+b)^2n 不是回文则停止；否则，让磁带处于类似 D (c+d)^3n D* 的状态

    1. 向右移。
    2. 如果磁带是 a（或 b），则向右移动。如果磁带是 c 或 d，则转到磁带的开头，然后转到步骤 3。
    3. 如果磁带是 c、d 或空白，则停止拒绝。否则，请向右扫描，直到找到 ac、d 或空白。向左移动。
    4. 如果磁带是 ab（或 a），则停止拒绝。否则，将其更改为 ac（或 d），然后向左扫描，直到看到空白、ac 或 a d。向右移。将 a（或 b）更改为 c（或 d）。向右移。
    5. 从第 2 步开始重复。

第 3 步将按如下方式进行

  • 前提条件：磁带为 D (c+d)^3n D*

  • 后置条件：磁带为 D (0+1)^3n D*

    1. 向右移。
    2. 如果磁带是 c，则写入 0 并向右移动。如果磁带是 d，写 1 并向右移动。如果磁带是空白的，则移动到磁带末尾的第一个空白处，然后转到步骤 4。
    3. 重复步骤 2。

第 4 步和第 5 步的工作方式与第 1 步和第 2 步相同，只是您向后工作（磁带现在看起来像 D (c+d)^n (a+b)^2n D*，您必须检查 (a +b)^2n 部分是回文。

通过这两个测试的任何字符串都必须是 ww^R w 的形式，其中 w 在 (0+1)* 中。

于 2011-10-12T20:51:15.383 回答
2

作为提示，请注意对于某些 n，ww R w 的长度必须为 3n（因为每个字符恰好出现 3 次）。因此，您可以构建一个图灵机，它通过某种方式计算字符串的长度，使用它来确定三个字符串的边界在哪里，然后检查三个部分是否都具有适当的组成。如果您不能数出 3 个字符的倍数，您可以立即拒绝。

根据允许的 TM 类型，使用多轨或多磁带图灵机可能是最简单的，这样您就可以用一些额外的信息标记字母。

希望这可以帮助！

于 2011-10-03T03:11:15.093 回答
0

以下是我使用 2 个磁带和 O(n) 复杂度的方法：

  1. 通过在磁带 1 中每 3 步向右移动磁带 2 的同时扫描磁带 1，确保长度除以 3
  2. 如果您到达磁带 1 的末尾，而磁带 2 的下一步是向右移动足够数量的字母（可被 3 整除）
  3. 标记你在磁带 2 上找到的字母（这是前三分之一的结尾）
  4. 回滚到两个磁带的开头
  5. 遍历磁带 2 直到标记并返回到第二个三分之一
  6. 确认 WWR：将两个磁带移动到磁带 2 的末尾，然后将磁带 1 向前移动，将磁带 2 向后移动。如果它们匹配，您将获得 WWR
  7. 检查开头和结尾的 W：只需在磁带 1 上继续扫描，同时从开头与磁带 2 进行比较
于 2021-07-11T09:13:41.567 回答