构建图灵机来决定ww ^ Rw

Question

w ^ R是w的反向,w是{0,1}*.因此,TM需要决定一个单词,然后是该单词的反向,后跟单词.我不想要答案,我只想要领先一步并走上正轨.

Answer 1

由于时间已过,可能不再需要答案,我想我会提出一个解决方案,为未来的学生寻找一个图灵机如何识别一种语言的例子.

这是个主意.我们将把磁带字母{0,1,a,b,c,d}作为一个单磁带单无限磁带图灵机来识别ww ^ R w.该机器将分五个阶段工作:

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

请注意,这只是一种简单的方法(我理解,就是这样),表明存在图灵机来识别这种语言.当然,表明在任何图灵等效计算系统中存在一种解决这个问题的算法同样好(它证明存在TM)......但是,这仍然概括了一个这样的TM的构造.还要注意,可能有一个更简单,更有效或更直观的TM来解决这个问题......再次,这只是一种方法.

第1步将如下工作:

• 前提条件:磁带以空白开头,包含(0 + 1)*中的任何字符串,后跟无限长的空白方块.

• 后置条件:如果磁带为空或长度不是3的倍数,则暂停; 否则,磁带以空白开头,然后是(a + b)^ 2n(c + d)^ n,接着是无限长的空白串.

  1. 向右移动.
  2. 如果为空,则停止接受.否则,向右扫描直至找到空磁带方块,然后向左移动.
  3. 如果为0则将磁带更改为c,如果为1则将磁带更改为
  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则将磁带更改为
  9. 向左扫描,直到找到a或b.向右移.
  10. 从4开始重复.

第2步将如下工作:

• 前提条件:磁带以空白开头,后跟(a + b)^ 2n(c + d)^ n,然后是无限长的空白字符串.

• 后置条件:如果前缀(a + b)^ 2n不是回文,则停止; 否则,使磁带处于D(c + d)^ 3n D*状态

  1. 向右移.
  2. 如果磁带是(或b),则向右移动.如果磁带为c或d,请转到磁带的开头,然后转到步骤3.
  3. 如果磁带是c,d或空白,则停止拒绝.否则,向右扫描直至找到ac,d或空白.向左移动.
  4. 如果磁带是ab(或a),则停止拒绝.否则,将其更改为ac(或d)并向左扫描,直到看到空白,ac或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)*中.

Answer 2

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

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

希望这可以帮助！