设计一个 TM 来计算两个一元数的加法

一元输入数字 n 用符号 0 表示 n -次。

示例

  • 4 → 0000

  • 1 → 0

  • 5 → 00000

分隔符“#”（任何其他特殊字符）应用于区分两个或多个输入。

例如：5、2 是由 00000 # 00 表示的输入。

算法

第 1 步 - 无替换地读取第一个输入的符号并向右移动。

第 2 步 - 当符号 = ‘#’ 时，将其替换为 ‘0’ 并向右移动。

第 3 步  - 向右遍历到最右边的 ‘0’（B – 最后一个符号的左边）

第 4 步 - 将最右边的 ‘0’ 替换为 B

第 5 步 - 停止机器。

图灵机

图灵机 (TM) 如下 -

图灵机，M 由 M = (Q, ∑, Γ, δ, q0, B, F) 给出

其中，

  • Q = {q0, q1, q2, q3}

  • Σ = {0, #}

  • Γ = {0, #, B}

  • δ ⇒ 由上述转换图 q 给出

  • 0 = {q0}

  • B = {B}

  • F = {q3}

更新于： 15-6-2021

8K+ 浏览量

开始你的职业生涯

通过完成课程来获得认证

开始吧
广告