如何制作{w∈{a，b}∗| 2na(w) = 3nb(w)}的图灵机。我的问题是如何应用条件
如何制作{w∈{a，b}∗| 2na(w) = 3nb(w)}的图灵机。我的问题是如何应用条件
提问于 2019-03-23 01:57:48
这是我对一个模块的赋值。我了解图灵机，对我来说问题是如何确保比率保持不变。我可以看到，如果我们可以检查每5位数字，而不是混合(例如{aababaabab})，而是像{aaaaaabbbb}这样的单词，那么人们将如何检查这一点。非常迷茫。
有什么建议/帮助吗？
回答 1
Stack Overflow用户
发布于 2019-03-23 05:02:34
我假设这意味着比率n/m = 3/2，其中n是a的出现次数，m是b的出现次数。
要解决一般情况，有很多可能的解决方案；这里有一种可能很容易理解。
从左到右扫描
- ，找到3个a。跳过A、b和b。将找到的3个a更改为A，然后返回到磁带的开头。如果您到达磁带的末尾而没有跨越任何a或b，请按halt-accept。如果你已经看到了一些a和b，但至少没有看到三个a，那么就停止-reject。否则，请继续执行步骤2.从左到右扫描，找到2个b。跳过A、B和a。将找到的两个b更改为B，然后返回到磁带的开头。如果到达终点时没有看到至少两个b，则使用halt-reject组合键。从步骤1开始重复，直到停止-接受或停止-拒绝。
示例：
aababaabab aaaaaabbbb aaaaabbbb
AAbAbaabab AAAaaabbbb AAAaabbbb
AABABaabab AAAaaaBBbb AAAaaBBbb
AABABAAbAb AAAAAABBbb halt_reject
AABABAABAB AAAAAABBBB
halt_accept halt_accept页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55305373
复制相关文章
相似问题
腾讯云开发者
