2

我想制作一个图灵机，它接受长度为 3 的 1 的字符串。111、111111111、111111111111111111111111111，依此类推。但我无法为此制定算法。到目前为止，我能够制造可以接受长度为 3 的倍数的机器。请帮助我

4

2 回答 2

3

与任何编程任务一样，您的目标是将任务分解为您可以解决的较小问题，解决这些问题，然后将各个部分组合在一起以解决更难的问题。一般来说，有很多方法可以做到这一点，你只需要找到一种对你有意义的方法。然后，只有到那时，您才应该担心获得“更好”、“更快”的程序。

是什么使数字成为三的幂？

  1. 第一是三的幂 (3^0)
  2. 如果一个数字是三的幂，则该数字的三倍是三的幂 (x = 3^k => 3x = 3^(k+1))。

我们可以“反转”上面 2 的方向，以给出递归而非归纳定义：一个数是 3 的幂，如果它可以被 3 整除并且该数除以 3 是 3 的幂：(3 | x && x / 3 = 3^k => x = 3^(k+1))。

这表明图灵机的工作方式如下：

  1. 检查磁带是否只有一个。如果是这样，停止接受。
  2. 否则，除以三，将磁带头重置到开头，然后重新开始。

我们如何除以三？好吧，我们可以先数一个，然后再抹掉两个；假设我们最终擦除的数量是我们计算的两倍，我们将拥有原始数量的三分之一。但是，如果我们用完了要擦除的数字，我们知道这个数字不能被三整除，我们可以停止拒绝。

这是我们的设计。现在是实施的时候了。我们将有两个阶段：第一阶段将检查单个的情况；另一个阶段将除以三并重置磁带头。当我们划分时，我们将通过引入一个新的磁带符号 B 来擦除一个，我们可以将其与空白单元格 # 区分开来。这很重要，因此我们可以记住输入的开始和结束位置。

Q    T    |    Q'    T'    D
----------+-----------------
// phase one: check for 3^0
----------+-----------------
q0   #    |    h_r   #     S    // empty tape, not a power of three
q0   1    |    q1    1     R    // see the required one
q0   B    |    h_r   B     S    // unreachable configuration; invalid tape
q1   #    |    h_a   #     L    // saw a single one; 1 = 3^0, accept
q1   1    |    q2    1     L    // saw another one; must divide by 3
q1   B    |    q1    B     R    // ignore previously erased ones
----------+-----------------
// prepare for phase two
----------+-----------------
q2   #    |    q3    #     R    // reached beginning of tape
q2   1    |    q2    1     L    // ignore tape and move left
q2   B    |    q2    B     L    // ignore tape and move left
----------------------------
// phase two: divide by 3
----------------------------
q3   #    |    q6    #     L    // dividing completed successfully
q3   1    |    q4    1     R    // see the 1st one
q3   B    |    q3    B     R    // ignore previously erased ones
q4   #    |    h_r   #     S    // dividing fails; missing 2nd one
q4   1    |    q5    B     R    // see the 2nd one
q4   B    |    q4    B     R    // ignore previously erased ones
q5   #    |    h_r   #     S    // dividing fails; missing 3rd one
q5   1    |    q3    B     R    // see the 3rd one
q5   B    |    q5    B     R    // ignore previously erased one
----------+-----------------
// prepare for phase one
----------+-----------------
q6   #    |    q0    #     R    // reached beginning of tape
q6   1    |    q6    1     L    // ignore tape and move left
q6   B    |    q6    B     L    // ignore tape and move left

可能有一些错误，但我认为这个想法应该基本上是合理的。

于 2017-11-06T14:10:11.340 回答
-1

检查输入的长度 (111, 111111111,...) 说 strLen。检查以 3 为底的 log(strLen) 的结果是否等于整数。

即，在代码中：

bool is_integer(float k) { return std::floor(k) == k; }

if(is_integer(log(strLen)/log(3))){ //Then accept the string as it's length is a power of 3. }

于 2017-11-05T10:45:13.777 回答