0

请给我一些关于如何去做的想法

画一个图灵机（使用 Sipser 表示法），它至少有 4 个非平凡（即非拒绝）状态和至少 6 个非平凡（即，非拒绝状态）转换。

4

1 回答 1

2

图灵机具有：

  • 有限数量的状态，其中一个是接受，一个是拒绝。该任务显然需要五个状态（四个不拒绝（其中一个必须接受）和一个拒绝）。这些州通常被画成圆圈，每个里面都有一个标签（州名）。其中一种状态是起始状态；它标有指向它的箭头。
  • 一个有限的输入字母表。{0, 1} 或 {a, b} 是典型的选择。
  • 一个有限的磁带字母表，其中包括一个特殊的空白符号、输入字母表中的所有符号，以及可能更多的符号（但这不是必需的）。
  • 为状态和磁带符号的每个组合分配状态、磁带符号和方向的转换函数。方向可以是 L（左）或 R（右）。转换被绘制为从一个状态到另一个状态的箭头（或者可能是从一个状态返回到自身的圆形箭头），并且箭头标有两个带符号以及 L 或 R。显然，您需要六个这样的箭头。

这台机器还有一个无限的磁带，它被分成多个单元。在每个单元格中，可以有一个来自磁带字母表的符号。最初出现在磁带上的符号称为机器的输入。该机器有一个读取头，它始终位于其中一个单元的上方。假设您有一个从状态 A 到状态 B 的转换箭头，上面有符号 a、b 和 R。这意味着：“如果机器处于状态 A 并且磁头下方的符号是 a，那么我们应该用 b 替换该符号，进入状态 B，并将读取磁头向右移动一个单元格。”

于 2011-02-24T20:14:35.707 回答