枚举器的图灵机图

问题描述 投票:1回答:3

我应该为语言0 ^ k1 ^ k(k> = 0)绘制一个枚举器。我不确定这与为这种语言构建图灵机状态图有什么不同:我理解它的方式是我需要通过模拟图灵来构建一个枚举器,该枚举器通过{0,1}以上的所有字符串识别上述语言在字符串i上为i步识别这种语言的机器,我无法想到如何使用状态图,但我的老师已经指出这是我们如何证明枚举器和图灵机之间的等价,所以我认为我们要做的是使用为枚举器定义的转换函数,这使得图表看起来类似于识别0 ^ k1 ^ k的图灵机,而不是移动到qaccept我们移动到qprint以获取语言中的输入,并且那么对于必须拒绝的输入我们打印epsilon?但是我们如何在字母{0,1}之上产生无限数量的字符串呢?在初始状态下,工作胶带和打印带是空的。有人可以为我澄清这些要点吗?也许我误解了。

turing-machines
3个回答
3
投票

我想我终于有了清晰的枚举器概念,一个枚举器不应该读取输入,它会用它构建的语言创建单词:这是算法:

  1. 在输出磁带上打印epsilon
  2. 在工作磁带上写01
  3. 返回到磁带的前面并将其内容复制到输出磁带
  4. 回到最左边的0,用1代替它,转到最右边的1并在末尾添加两个1。
  5. 回到第3阶段


1
投票

我想到了另一种略有不同的算法,它产生的状态数较少,并且在其工作磁带上仅使用{0,blank}:


0
投票

我想你可能有错误。在第4阶段,你写了“回到最左边的0,用1替换它,到最右边的1并在末尾添加两个1”我认为它应该是:“回到最左边的1,用0替换它,转到最右边1并在末尾添加两个1'

© www.soinside.com 2019 - 2024. All rights reserved.