我应该为语言0 ^ k1 ^ k（k> = 0）绘制一个枚举器 . 我不确定这与为这种语言构建图灵机状态图有什么不同：我理解它的方式是我需要通过模拟图灵来构建一个枚举器，该枚举器通过{0,1}以上的所有字符串识别上述语言在字符串i上为i步骤识别这种语言的机器，我无法想象如何使用状态图，但我的老师已经指出这是我们如何证明枚举器和图灵机器之间的等价，所以我认为我们要做的是使用为枚举器定义的转换函数，这使得图表看起来类似于识别0 ^ k1 ^ k的图灵机，而不是移动到qaccept，我们移动到qprint以获取语言中的输入，并且那么对于必须拒绝的输入我们打印epsilon？但是我们如何在字母{0,1}之上产生无限数量的字符串呢？在初始状态下，工作胶带和打印带是空的 . 有人可以为我澄清这些要点吗？也许我误解了 .
2 回答
我想到了另一种略有不同的算法，它产生的状态数较少，并且在其工作磁带上仅使用{0，blank}：
我想我终于有了清晰的枚举器概念，一个枚举器不应该读取输入，它用它构建的语言创建单词：这是算法：
在输出磁带上打印epsilon
在工作磁带上写01
返回到磁带的前面并将其内容复制到输出磁带
返回最左边的0，将其替换为1，转到最右边的1并在末尾添加两个1 .
回到第3阶段