我應該畫一個語言爲0^k1^k(k> = 0)的枚舉器。我不確定與爲這種語言構建圖靈機狀態圖有什麼不同:我理解它的方式是我需要通過模擬圖靈來構建一個枚舉器,該枚舉器通過給定{0,1}上的所有字符串來識別上述語言機器在字符串i上識別這種語言的步驟,我無法考慮如何使用狀態圖,但我的老師指出這是我們如何證明枚舉器和圖靈機之間的等價關係,所以我認爲我們要做的就是使用爲枚舉數定義的轉換函數,這使得圖看起來類似於識別0^k1^k的圖靈機,而不是移動到q代表我們移動到qprint用於語言輸入,並且那麼對於必須被拒絕的投入,我們會打印epsilon?但是我們如何去在字母{0,1}上面生成無限數量的字符串呢?在初始狀態下,工作膠帶和打印膠帶是空的。有人能爲我澄清這些問題嗎?也許我誤解了。統計員的圖靈機圖
Q
統計員的圖靈機圖
1
A
回答
2
我想我終於有枚舉概念清晰,枚舉不應該讀的輸入,它會在語言的話,這就是它內置: 這裏的算法:
- 打印小量的輸出帶
- 工作的磁帶上寫01
- 回到磁帶的前部,將其內容複製到輸出磁帶
- 回到最左邊的0,1取代它,去到最右邊1並在最後添加兩個1。
- 回到階段3
1
我認爲會略有不同的算法產生狀態的數量較少,並在其工作的磁帶只使用{0,空}:
相關問題
- 1. 設計圖靈機
- 2. 圖靈機設計
- 3. 計算理論圖靈機
- 4. 上圖靈機
- 5. 圖靈機設計0和1
- 6. 平方根計算圖靈機
- 7. 圖靈機配置
- 8. DPDA到圖靈機?
- 9. 圖靈機停機問題
- 10. 圖靈機器和機器圖解
- 11. 素數的圖靈機
- 12. 用圖靈機指定給定序列的成員
- 13. 圖靈機與模式
- 14. 圖靈機模擬器
- 15. 通用圖靈機示例
- 16. 圖靈機MOD功能
- 17. 非確定性圖靈機
- 18. 如何模擬圖靈機?
- 19. 設計一個圖靈機的狀態表
- 20. 創建一個特定的圖靈機
- 21. JFLAP圖靈機的批量測試
- 22. 圖靈機:取兩個數字的mod?
- 23. Hazelcast地圖統計
- 24. 基於constexpr的計算圖靈完整?
- 25. erlang系統的設計圖(圖)
- 26. 靈活的圖像視圖
- 27. 圖靈機接受總理長度
- 28. 圖靈機和想出一個想法
- 29. 圖靈機 - 更多0或1?
- 30. 如何將CFG轉換爲圖靈機
枚舉器構造屬於該語言的字符串,不接受/拒絕 – 2010-11-14 16:11:14
否,但它會打印圖靈機接受的語言並具有轉換功能。 – Noona 2010-11-14 18:09:39