我应该为语言 0^k1^k (k>=0) 绘制一个枚举器。我不确定这与为该语言构建图灵机状态图有何不同：我理解它的方式是，我需要构建一个枚举器，通过模拟图灵，在给定所有高于 {0,1} 的字符串的情况下，我需要构建一个能够识别上述语言的枚举器机器在 i 步骤中识别字符串 i 上的这种语言，我想不出如何使用状态图来做到这一点，但我的老师指出，这就是我们如何证明枚举器和图灵机之间的等价性，所以我认为我们必须做的是使用为枚举器定义的转换函数，这使得图表看起来类似于识别 0^k1^k 的图灵机，只是我们没有移动到 qaccept，而是移动到 qprint 以获取语言中的输入，然后对于必须拒绝的输入，我们打印 epsilon? 但是我们如何在字母表 {0,1} 之上产生无限数量的字符串呢？在初始状态，工作带和打印带是空的。有人可以为我澄清这些观点吗？也许我误解了。
问问题
6571 次
3 回答
4
我想我终于清楚了枚举器的概念，枚举器不应该读取输入，它会以构建它的语言创建单词：这是算法：
- 在输出磁带上打印 epsilon
- 在工作磁带上写 01
- 回到磁带的前面并将其内容复制到输出磁带
- 回到最左边的0，用1代替，到最右边的1，最后加两个1。
- 回到第 3 阶段
于 2010-11-15T15:25:47.560 回答
1
我想到了另一种稍微不同的算法，它产生的状态数量较少，并且在其工作磁带上仅使用 {0,blank}：
于 2010-11-15T17:43:18.490 回答
0
我想你可能有一个错误。在第4阶段，你写了“回到最左边的0，用1替换，到最右边的1并在最后添加两个1”我认为应该是：“回到最左边的1，用0替换, 到最右边的 1 并在末尾添加两个 1"
于 2019-03-14T14:46:17.573 回答