数据结构
网络
关系数据库管理系统 (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+ 次浏览
广告