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

在這裡，我們將瞭解如何為語言 L = {WW^r |W 屬於 {0, 1}} 構建圖靈機。所以這表示一種語言，我們只使用兩個字元 0 和 1。w 是一個字串，w^r 是它的逆序。所以如果 w = 10110，那麼 w^r 將是 01101。因此，圖靈機將接受字串 z = 1011001101。

為了解決這個問題，我們將使用這種方法。首先檢查第一個符號，如果它是 0，則使用 y 替換它，如果它是 1，則使用 x 替換它。然後轉到字串的末尾。所以最後一個符號與第一個符號相同。我們也根據它用 x 或 y 替換它。之後，再次回到從開始替換的符號旁邊的位置，並重覆上述相同過程。我們必須記住，由於 w^r 是 w 的逆序，因此兩者將具有相同數量的符號。每次替換字串開頭處的第 n 個符號時，都替換結尾處的相應第 n 個符號。

狀態轉換圖

Arnab Chakraborty

更新於: 2020年1月3日

5K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

立即開始