構造一個圖靈機 (TM)，識別形如 aⁿbⁿcⁿ (n≥1) 的字串，其中 Σ = {a, b, c}。

演算法

步驟 1：處理最左邊的“a”，將其替換為“x”。

步驟 2：向右移動，直到到達最左邊的“b”，將其替換為“y”。

步驟 3：向右移動，直到到達最左邊的“c”，將其替換為“z”。

步驟 4：向左移動，到達最左邊的“a”，並執行步驟 1、2 和 3 (n – 1) 次。

步驟 5：如果存在 n 個 x、y、z，則停止。

給定語言的圖靈機如下：

圖靈機 M 定義為 M = (Q, Σ, Γ, δ, q0, B, F)

其中：

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

• Σ = {a, b, c}

• Γ = {a, b, c, x, y, z, B}

• δ ⇒ 由 TM 的狀態轉換圖給出

• q0 = {q0}

• B = {B}

• F = {q5}

Bhanu Priya

更新於：2021年6月15日

瀏覽量：552

啟動你的職業生涯

完成課程獲得認證

開始學習