設計一個 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+ 瀏覽量

開始你的職業生涯

透過完成課程來獲得認證

開始吧