设计一个识别Σ={a, b}上回文串的图灵机。

算法

步骤1 - 如果没有输入，则到达最终状态并停止。

步骤2 - 如果输入 = “a”，则向前遍历以处理最后一个符号 = “a”。将两个“a”都转换为“B”。

步骤3 - 向左移动以读取下一个符号。

步骤4 - 如果输入 = “b”，则将其替换为“B”，并向右移动以处理其在最右端的等效“B”。

步骤5 - 将最后一个 'b' 转换为 'B'。

步骤6 - 向左移动并处理步骤 2-5，直到没有更多输入需要处理。

步骤7 - 如果机器在处理整个输入字符串后到达最终状态，则该字符串是回文串，这将使机器停止。

图灵机

图灵机如下：

图灵机 M 定义为 M = (Q, Σ, Γ, δ, q0, B, F)

其中：

  • Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8}

  • Σ = {a, b}

  • Γ = {a, b, B}

  • δ ⇒ 由上述状态转换图给出

  • q0 = {q0}

  • B = {B}

  • F = {q8}

考虑字符串 aabbaa，如下所示：

更新于：2021年6月15日

21K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告