设计接受语言 L= {a^n+1 b^2n c^3n: n>=0} 的图灵机
Design a turing machine that accepts the language L= {a^n+1 b^2n c^3n: n>=0}
我需要一些帮助来设计接受语言的图灵机
L= {a^n+1 b^2n c^3n: n>=0}
有很多正确的方法可以做到这一点。我将只介绍其中一个，希望能说明一种解决这些问题的有用方法。
首先，我们注意到三个部分之间的共性 n。我们将划掉每个部分的符号，一次一个，以确保它们具有正确的关系。首先，我们可以验证a和b之间的关系是否正确。然后，我们可以检查 a 和 c 之间的关系。如果这些都正确，我们就完成了。
首先，让我们去掉 a 中讨厌的“+1”。这意味着无论 n 是多少，我们至少有一个 a。因此，我们可以从将 a 更改为 X 开始。现在，剩余的输入应该有 n 个 a 实例、2n 个 b 实例和 3n 个 c 实例。如果我们没有a，我们可以立即halt-reject；如果我们没有至少一个，我们就不能有 n+1 个实例。
现在，如果有更多的 a 实例，通过在其位置上写 A 将其划掉，并通过在它们的位置上写 B 来划掉 b 的两个实例。然后，返回并寻找更多的 a 实例，来回跳动直到没有更多的 a 实例。然后，验证不再有 b 的实例；如果是这样，则 b 的实例数是 a 的两倍，并且前两部分具有正确的关系。如果在任何时候你没有足够的 b 来划掉，或者如果在你 运行 从 a 中你仍然有 b，那么你可以安全地 halt-reject 在这一点上。
接下来，您可以对 A 和 c 的实例执行相同的操作，只需划掉 c 的三个实例而不是两个。如果我们发现 A 和 c 同时筋疲力尽，我们就完了 halt-accept.
第运行站可能如下所示：
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
因为我们不应该解决你的作业:)，我在 JFLAP 上解决了以下语言，你可以为你的语言稍微改变一下。逻辑是一样的，您需要添加几个状态。
L = {a^n+1 b^2n : n >= 0}
我需要一些帮助来设计接受语言的图灵机 L= {a^n+1 b^2n c^3n: n>=0}
有很多正确的方法可以做到这一点。我将只介绍其中一个，希望能说明一种解决这些问题的有用方法。
首先，我们注意到三个部分之间的共性 n。我们将划掉每个部分的符号，一次一个，以确保它们具有正确的关系。首先，我们可以验证a和b之间的关系是否正确。然后，我们可以检查 a 和 c 之间的关系。如果这些都正确，我们就完成了。
首先，让我们去掉 a 中讨厌的“+1”。这意味着无论 n 是多少，我们至少有一个 a。因此，我们可以从将 a 更改为 X 开始。现在，剩余的输入应该有 n 个 a 实例、2n 个 b 实例和 3n 个 c 实例。如果我们没有a，我们可以立即halt-reject；如果我们没有至少一个，我们就不能有 n+1 个实例。
现在，如果有更多的 a 实例，通过在其位置上写 A 将其划掉，并通过在它们的位置上写 B 来划掉 b 的两个实例。然后，返回并寻找更多的 a 实例，来回跳动直到没有更多的 a 实例。然后，验证不再有 b 的实例；如果是这样，则 b 的实例数是 a 的两倍，并且前两部分具有正确的关系。如果在任何时候你没有足够的 b 来划掉，或者如果在你 运行 从 a 中你仍然有 b，那么你可以安全地 halt-reject 在这一点上。
接下来，您可以对 A 和 c 的实例执行相同的操作，只需划掉 c 的三个实例而不是两个。如果我们发现 A 和 c 同时筋疲力尽，我们就完了 halt-accept.
第运行站可能如下所示：
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
因为我们不应该解决你的作业:)，我在 JFLAP 上解决了以下语言，你可以为你的语言稍微改变一下。逻辑是一样的，您需要添加几个状态。 L = {a^n+1 b^2n : n >= 0}