我需要一些帮助来设计接受语言 L= {a^n+1 b^2n c^3n: n>=0} 的图灵机
问问题
1313 次
2 回答
1
有很多正确的方法可以做到这一点。我将只介绍其中一个，希望能说明解决这些问题的有用方法。
首先，我们注意到三个部分之间的共性 n。我们将划掉每个部分的符号，一次一个，以确保它们具有正确的关系。首先，我们可以验证 a 和 b 之间的关系是否正确。然后，我们可以检查 a 和 c 之间的关系。如果这两个都是正确的，我们就完成了。
首先，让我们从 a 中去掉讨厌的“+1”。这意味着无论 n 是什么，我们都至少有一个 a。因此，我们可以从将 a 更改为 X 开始。现在，剩余的输入应该有 a 的 n 个实例、b 的 2n 个实例和 c 的 3n 个实例。如果我们没有a，我们可以立即停止-拒绝；如果我们没有至少一个，我们就不能有 n+1 个实例。
现在，如果有更多的 a 的实例，在它的位置写上 A 来划掉它，然后在它们的位置写上 B 来划去 b 的两个实例。然后，返回并寻找更多的 a 实例，来回弹跳直到不再有 a 的实例。然后，验证没有更多的 b 实例；如果是这样，则 b 的实例数量是 a 的两倍，并且前两个部分具有正确的关系。如果在任何时候你没有足够的 b 来划掉，或者在你用完 a 之后你仍然有 b，那么你可以安全地停止-拒绝。
接下来，您可以对 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 end
于 2019-05-29T14:10:02.260 回答
1
由于我们不应该解决您的作业:)，我在 JFLAP 上解决了以下语言，您可以根据您的语言对其进行一些更改。逻辑是相同的，您需要添加几个状态。L = {a^n+1 b^2n : n >= 0}
于 2019-06-10T10:40:19.513 回答