构造一个图灵机 (TM)，以二进制数作为输入，并将最后一位替换为其布尔补码。

问题

设计一个图灵机 (TM)，它接收一个二进制数作为输入，并将字符串的最后一位替换为其布尔补码。

解决方案

图灵机是一个7元组 (Q, ∑, Γ, δ, q0, qaccept , qreject)

其中：

  • Q 是有限状态集。

  • ∑ 是输入字母表，不包含空格符 t。

  • Γ 是带字母表，其中 t ∈ Γ 且 ∑ ⊆ Γ。

  • δ − (Q × Γ) → (Q × Γ × {L, R}) 是转移函数。

  • q0 ∈ Q 是起始状态。

  • qaccept ∈ Q 是接受状态。

  • qreject ∈ Q 是拒绝状态，其中 qreject ≠ qaccept。

在这个图灵机中：

  • 在状态 q0，我们将读取所有输入，直到遇到空格符。

  • 如果找到空格，我们向左移动一位。

  • 现在，我们有两个选择：最后一位是 0 或 1。

    • 如果是 0，则将其替换为 1，反之亦然。

  • 状态 q4 是最终状态。

如果将二进制数作为输入，并将字符串的最后一位替换为其布尔补码，则图灵机如下所示。

更新于：2021年6月16日

270 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习
广告