如何將DFA轉換爲圖靈機？

有了DFA圖，我該如何將它轉換爲圖靈機？我是否必須找到DFA接受的語言，然後創建圖靈機？或者有直接的方法嗎？如何將DFA轉換爲圖靈機？

謝謝。

2013-12-11 user2880113

DFA中的每個轉換都會讀取輸入字符，執行轉換，然後轉到輸入的下一個字符。一旦讀取完所有輸入，如果DFA處於接受狀態並接受其他拒絕，則接受DFA。

你可以用圖靈機直接模擬這個。通過爲DFA中的每個狀態創建一個狀態，構建圖靈機的有限狀態控制。對於字符c上的DFA中的每個轉換，將TM中的轉換替換爲在讀取字符c時將某些任意字符寫回到磁帶（無所謂），然後向右移動磁帶頭（到磁帶上的下一個位置）。然後，對於每個狀態，將空白符號從該狀態轉換到TM的接受狀態或TM的拒絕狀態（基於該狀態是接受還是拒絕）。該TM通過在輸入字符串中手動步進來有效地運行DFA，並最終決定在運行結束時是接受還是拒絕。

希望這會有所幫助！

來源

2013-12-11 06:18:28 templatetypedef

當發生字符c被讀取時不會導致狀態轉換的情況？是否寫入任意字符並且磁帶頭仍然向右移動？ – Paradox

@Paradox在DFA的大多數定義中，DFA必須爲每個字符和每個狀態定義一個轉換。同樣，大多數TM都是通過一種方式來定義的，它允許您限制可以輸入什麼樣的符號，因此您永遠不必擔心：可能遇到的任何TM符號都是DFA可能會遇到的過渡定義。或者，如果您沒有此限制，只需拒絕 - DFA的語言僅限於使用其字母中的字符，因此如果看到外部字符，則知道字符串不在該語言中。 – templatetypedef

如何將DFA轉換爲圖靈機？

回答

相關問題