枚举器的图灵机图
我应该为语言 0^k1^k (k>=0) 绘制一个枚举器。我不确定这与为这种语言构建图灵机状态图有什么不同：我理解的方式是，我需要构建一个枚举器，通过模拟图灵机，在给定所有高于 {0,1} 的字符串的情况下识别上述语言机器在字符串 i 上识别这种语言，持续 i 个步骤，我不知道如何使用状态图来做到这一点，但我的老师指出，这就是我们证明枚举器和图灵机之间等价性的方法，所以我认为我们要做的是使用为枚举器定义的转换函数，这使得图看起来类似于识别 0^k1^k 的图灵机，只是我们不是转向 qaccept，而是转向 qprint 来输入语言，并且那么对于必须拒绝的输入，我们打印 epsilon？但是我们如何在字母表 {0,1} 之上生成无限数量的字符串呢？在初始状态下，工作带和打印带是空的。有人可以帮我澄清这些要点吗？也许我误解了。
I am supposed to draw an enumerator for the language 0^k1^k (k>=0). I am not sure how that is different from building a Turing machine state diagram for this language: the way I understand it is that I need to build an enumerator that recognizes the aforementioned language given all strings above {0,1} by simulating the Turing machine that recognizes this language on string i for i steps, which I couldn't think how to do using a state diagram, but my teacher has pointed out that this is how we prove the equivalence between an enumerator and a Turing machine, so I thought that what we have to do is use the transition function defined for enumerators which makes the diagram look similar to the Turing machine that recognizes 0^k1^k, only instead of moving to qaccept we move to qprint for inputs in the language, and then for inputs that must be rejected we print epsilon? But how do we go about producing an infinite number of strings above the alphabet {0,1}? At the initial state the work tape and the print tape are empty. Can someone clarify these points for me? Maybe I misunderstand.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我想我终于清楚了枚举器的概念，枚举器不应该读取输入，它用它所构建的语言创建单词：
算法如下：
I think I finally have the enumerator notion clear, an enumerator is not supposed to read an input, it creates words in the language for which it is built:
here's the algorithm:
我想到了另一种稍微不同的算法，它产生较少数量的状态，并且在其工作磁带上仅使用 {0,blank} ：
i thought of another slightly different algorithm that produces a smaller number of states, and uses only {0,blank} on its work tape:
我认为你可能有一个错误。
在第 4 阶段，你写了“返回到最左边的 0，将其替换为 1，转到最右边的 1，并在末尾添加两个 1”
我认为应该是：“返回到最左边的1，将其替换为0，转到最右边的1并在末尾添加两个1”
i think you might have an error there.
in stage 4, you wrote "go back to the leftmost 0, replace it with 1, go to the rightmost 1 and add two 1's at the end"
i think it should be: "go back to the leftmost 1, replace it with 0, go to the rightmost 1 and add two 1's at the end"