“如何制作{w∈{a，b} * |的图灵机2na（w）= 3nb（w）}。我的问题是如何应用条件“

Question

这是我对模块的一项任务。我理解图灵机，对我来说问题是如何确保比例保持不变。我可以看到如果我们可以检查每5个数字而不混合（例如{aababaabab}），但是对于像{aaaaaabbbb}这样的单词，我们将如何检查这个。很丢失。

任何提示/帮助？

Answer 1

我认为这意味着比率n / m = 3/2，其中n是a的出现次数，m是b的出现次数。

为了解决一般情况，可以提供许多解决方案;这是一个可能很容易理解的。

1. 从左到右扫描，找到3次出现。跳过A，B和b。将您找到的三个更改为A并返回到磁带的开头。如果你碰到磁带的末端而没有越过任何a或b，则停止接受。如果你看到磁带的末端看到一些a和b但不是至少三个a，停止拒绝。否则，继续执行第2步。
2. 从左向右扫描，找到2次出现的b。跳过A，B和a。将找到的两个b更改为B并返回到磁带的开头。如果你在没有看到至少两个b的情况下到达终点，则停止拒绝。从步骤1开始重复，直到您停止接受或停止拒绝。

例子：

aababaabab    aaaaaabbbb     aaaaabbbb
AAbAbaabab    AAAaaabbbb     AAAaabbbb
AABABaabab    AAAaaaBBbb     AAAaaBBbb
AABABAAbAb    AAAAAABBbb     halt_reject
AABABAABAB    AAAAAABBBB
halt_accept   halt_accept