資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究設計一個圖靈機 (TM)，在 Σ = {0, 1} 上執行右移操作。
問題
將輸入字串向右移動一位，並設計一個圖靈機 (TM)，它可以在 Σ = {0, 1} 上執行右移操作。
解決方案
參考下面給出的演算法來設計一個 TM −
步驟 1 − 從初始字元移動到最後一個字元。
步驟 2 − 如果字元是“0”，將其替換為“B”，然後向右移動一步，將緊鄰的“B”替換為“0”。
步驟 3 − 如果字元是“1”，將其替換為“B”，然後向右移動一步，將緊鄰的“B”替換為“1”。
步驟 4 − 按照上述步驟處理後，向左移動一步，對下一個最右邊的未處理字元執行步驟 2 或 3。
步驟 5 − 重複步驟 4，直到所有字元都處理完畢。
下圖顯示了相應的 TM −
圖靈機描述
圖靈機由 M = (Q, Σ, Γ, δ, q0, B, F) 給出
其中，
Q = {q0, q1, q2, q3, q4, q5}
Σ = {0, 1}
Γ = {0, 1, B}
q0 = {q0}
B = {B}
F = {q5}
這裡，
q0 → 跳過初始的“0”和“1”，並將 TM 的磁頭移動到最後一個字元。q1 → 將未處理的最右字元替換為 B。
q2 → 在處理輸入“0”時，q2 立即將“B”替換為“0”並向左移動。
q3 → 在處理“1”時，q3 立即將“B”替換為“1”並向左移動。
q4 → 向左移動一個位置以處理下一個字元
q5 → 如果沒有更多輸入字元，則停止。
更新於：2021年6月14日
4K+ 次瀏覽
廣告