設計一個識別Σ={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，如下所示：

Bhanu Priya

更新於：2021年6月15日

21K+ 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習