设计一个接受语言L= {a^n+1 b^2n c^3n: n>=0}的图灵机
我需要一些帮助来设计图灵机，它接受语言L= {a^n+1 b^2n c^3n: n>=0}
回答 2
Stack Overflow用户
发布于 2019-05-29 22:10:02
有很多正确的方法可以做到这一点。我将只介绍其中一个，我希望这是解决这些问题的一种有用的方法。
首先，我们注意到三个段之间的共性n。我们将划掉每个部分的符号，一次一个，以确保它们具有正确的关系。首先，我们可以验证a和b之间的关系是正确的。然后，我们可以检查a和c之间的关系。如果这两个都是正确的，我们就完成了。
首先，让我们去掉a中令人讨厌的"+1“，这意味着不管n是什么，我们至少有一个a。现在，剩余的输入应该有a的n个实例，b的2n个实例和c的3n个实例。如果我们没有a，我们可以立即停止-拒绝；如果我们没有至少一个，我们就不能有a的n+1实例。
现在，如果有更多的a实例，通过在其位置上写A来划掉它，通过在b的位置上写B来划掉b的两个实例。然后，返回并查找a的更多实例，来回跳转，直到不再有a的实例。然后，验证是否不再有b的实例；如果是，则b的实例是a的两倍，并且前两个部分具有正确的关系。如果在任何时候你没有足够的b来删除，或者如果你用完了a，你仍然有b，那么你可以安全地在这一点上停止-reject。
接下来，您可以对A和c的实例执行相同的操作，只需划掉c的三个实例，而不是两个。如果我们发现a和c同时被耗尽，我们就完成并停止接受。
转换可能如下所示：
Q T Q' T' d comment
q0 a q1 X right account for +1
q1 a q2 A right n>0 case, continue
q1 # hA # same n=0 case, accept
q2 a q2 a right skip uncrossed a
q2 B q2 B right skip crossed b
q2 b q3 B right find first uncrossed b, cross it
q3 b q4 B left find next b, cross it
q4 B q4 B left find last uncrossed a
q4 a q2 A right cross it
q4 A q4 A left skip crossed a, if any
q4 X q5 X right ran out of a to cross
q5 A q5 A right skip crossed a
q5 B q5 B right skip crossed b
q5 c q6 c left verify existence of some c
q6 C q6 C left skip crossed c
q6 B q6 B left skip crossed b
q6 A q7 a right find last crossed a, uncross
q6 X q10 X right ran out of crossed a
q7 a q7 a right skip uncrossed a
q7 B q7 B right skip crossed b
q7 C q7 C right skip crossed c
q7 c q8 C right find first uncrossed c, cross
q8 c q9 C right cross 2nd uncrossed c
q9 c q6 C left cross 3rd uncrossed c
q10 a q10 a right skip uncrossed a
q10 B q10 B right skip crossed b
q10 C q10 C right skip crossed c
q10 # hA # same accept if no leftover symbols until endStack Overflow用户
发布于 2019-06-10 18:40:20
由于我们不应该解决您的作业:)，我在JFLAP上解决了以下语言，您可以针对您的语言稍作修改。逻辑是相同的，您需要添加几个状态。L= {a^n+1 b^2n :n >= 0}
https://stackoverflow.com/questions/56354448
复制相似问题
腾讯云开发者
