構造一個圖靈機來識別語言 L = {aibjck | i*j = k; i, j, k ≥ 1}

在這裡，我們將學習如何為語言 L = {AiBjCk | i * j = k; i, j, k ≥ 1} 建立一個圖靈機。這表示一種僅使用三個字元 A、B 和 C 的語言。w 是一個字串。因此，如果 w = AABBBBCCCCCCCC，則圖靈機將接受它。

為了解決這個問題，我們將採用以下方法。

  • 首先將一個 A 替換為 x 並向右移動。然後跳過所有 A 並向右移動。

  • 當磁頭到達第一個 B 時，將一個 B 替換為 y，然後向右移動，跳過所有中間的 B，並對應於被替換的 B，現在將一個 C 替換為 z 並向左移動。

  • 現在向左移動，跳過所有 z 和 B。

  • 當指標指向最近的 y 時，向右移動。

  • 如果指標指向 B，則重複步驟 2 到 4；否則，如果指標指向 z，則向左移動，同時將所有 y 替換為 B 並跳過所有 A。

  • 當指標到達最近的 x 時，向右移動。

  • 如果指標仍然指向 A，則重複上述所有步驟；否則，當磁頭位於 y 時，向右移動，跳過所有 y 和 z。

  • 當到達 $ 時，向左移動。字串被接受。

狀態轉換圖

更新於：2020年1月3日

1K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告