統計員的圖靈機圖

Question

我應該畫一個語言爲0^k1^k（k> = 0）的枚舉器。我不確定與爲這種語言構建圖靈機狀態圖有什麼不同：我理解它的方式是我需要通過模擬圖靈來構建一個枚舉器，該枚舉器通過給定{0,1}上的所有字符串來識別上述語言機器在字符串i上識別這種語言的步驟，我無法考慮如何使用狀態圖，但我的老師指出這是我們如何證明枚舉器和圖靈機之間的等價關係，所以我認爲我們要做的就是使用爲枚舉數定義的轉換函數，這使得圖看起來類似於識別0^k1^k的圖靈機，而不是移動到q代表我們移動到qprint用於語言輸入，並且那麼對於必須被拒絕的投入，我們會打印epsilon？但是我們如何去在字母{0,1}上面生成無限數量的字符串呢？在初始狀態下，工作膠帶和打印膠帶是空的。有人能爲我澄清這些問題嗎？也許我誤解了。

Answer 1

我想我終於有枚舉概念清晰，枚舉不應該讀的輸入，它會在語言的話，這就是它內置： 這裏的算法：

1. 打印小量的輸出帶
2. 工作的磁帶上寫01
3. 回到磁帶的前部，將其內容複製到輸出磁帶
4. 回到最左邊的0，1取代它，去到最右邊1並在最後添加兩個1。
5. 回到階段3

Answer 2

我認爲會略有不同的算法產生狀態的數量較少，並在其工作的磁帶只使用{0，空}：