構造一個圖靈機 (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 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習
廣告