構建非確定性圖靈機

Question

繪製雙磁帶非決定性圖靈機M的圖表，決定語言

L = {w∈Σ* | W =üüü∈Σ*}

如果我能得到幫助解釋步驟如何構建NDTM（語言），我相信我能畫出圖，但我不可能拿出一個答案..

謝謝

Answer 1

通過u*u*u（在編輯歷史看），我想你打算什麼形式的所有詞ü^ 3（U重複三次）的語言，其中u是任何串過字母表。

我們的NDTM需要至少以一種方式接受語言中的字符串，並且它絕不能接受任何不在語言中的東西。特別是，關鍵在於NDTM可以拒絕該語言中的字符串，只要通過NDTM的某個路徑確實接受該語言中的每個字符串即可。

鑑於此，我們的第一步可以猜到關於u的長度。 NDTM可以通過在確定掃描權限的任意點處從狀態q0到q1然後q2的非確定性轉變來標記三個磁帶符號（例如，通過寫入帶下劃線的符號版本）。然後，我們可以重置磁帶頭並使用確定性TM來回答這個問題：第一步我們猜到的分割是否會產生u^3的字符串？

這是確定性的，因爲我們知道零件的描繪。我們可以檢查前兩部分（例如，通過反彈和標記已經處理的符號），然後檢查後兩部分（使用相同的技術，但應用於第二和第三部分）。

我們已經將問題減少到檢查字符串是否爲w|w的形式，我們知道拆分。這種確定性TM更容易想出。當我們把它放在NDTM之後，猜測如何分割初始輸入時，我們得到一個NDTM，它可以（並且恰好一個猜測）接受u^3的任何字符串，但不可能接受任何其他的東西。這就是我們所追求的，我們完成了。