構造一個用於語言 L = {ww | w ∈ {0,1}} 的圖靈機。

在這裡，我們將學習如何為語言 L = {WW | W屬於{0, 1}} 建立一個圖靈機。這意味著我們將只使用兩個字元 0 和 1 來構建一種語言。w 是一個字串。所以如果 w = 10110，那麼圖靈機將接受字串 z = 1011010110。

為了解決這個問題，我們將採用這種方法。首先是找到字串的中點，我們將 0 轉換為 x，將 1 轉換為 y。持續進行此操作，直到所有 0 和 1 都分別轉換為 x 和 y。現在，我們到達了字串的中點。所以我們的第一個目標完成了。

現在，將中點左側的所有 x 和 y 轉換為 0 和 1。現在字串的前半部分是 0 和 1 的形式。字串的後半部分是 x 和 y 的形式。

現在，再次從字串的開頭開始。如果遇到 0，則將其轉換為 x 並向右移動，直到到達後半部分，如果在這裡找到 x，則將其轉換為空白 (B)。然後返回，直到找到 x 或 y。我們將它右邊的 0 或 1 分別轉換為 x 或 y，並相應地將字串後半部分的 x 或 y 轉換為空白 (B)。

繼續此操作，直到將字串左半部分的所有符號轉換為 x 和 y，並將字串右半部分的所有符號轉換為空白。如果一部分完全轉換，但另一部分仍有一些符號未更改，則該字串將不被接受。如果我們沒有在後半部分找到與前半部分的 0 或 1 分別對應的 x 或 y，則該字串也將不被接受。

狀態轉換圖

更新於：2020年1月3日

5K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告