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