如何从字母表创建一台机器
How to create a machine from alpabet
我在研究图灵机，
然后我遇到了一些问题。
a^m . a^3n . b^n
如何给本机设计状态图？
你能帮忙吗？
假设 m 和 n 之间没有关系，策略如下：
验证第一个周期之前的所有内容都是 a。如果您在进入第一期之前看到任何其他内容，请停止拒绝。除非假定 m > 0，否则将句号视为第一个输入符号是可以的。
如果您看到第二部分没有剩余的 a，请确认第三部分中没有剩余的 b，如果是，则停止接受。否则，如果还有 bs 剩余，halt-reject.
如果第二部分还剩下 a，请划掉其中三个 a。如果没有至少三个 a 要划掉，则暂停拒绝。如果有，那就划掉一个b。如果没有剩余的 b 可以划掉，则暂停拒绝。如果有 b，请返回第 2 部分并继续第 2 步，直到您停止接受或停止拒绝。
示例：
aa.aaaaaa.bb => aa.xxxaaa.xb => aa.xxxxxx.xx => halt-accept
aa.aaaaa.bb => aa.xxxaa.xb => halt-reject
aa.aaaaaa.bbb => aa.xxxaaa.xbb => aa.xxxxxx.xxb => halt-reject
aa.aaaaaa.b => aa.xxxaaa.x => aa.xxxxxx.x => halt-reject
ba.aaaaaa.bb => halt-reject
这些州可能看起来像这样：
state tape state' tape' direction comment
q0 a q0 a right read a's until you see
q0 . q1 . right a period, crash otherwise
q1 a q2 x right if you see a's, cross off
q1 x q1 x right the 1st of 3. skip x's and
q1 . q8 . right if you see . check for no b's
q2 a q3 x right read the 2nd of 3 a's
q3 a q4 x right read the 3rd of 3 a's
q4 a q4 a right skip over any remaining a's
q4 . q5 . right to get to the 2nd .
q5 b q6 x left cross off one b for the 3 a's
q5 x q5 x right skip over any x's
q6 x q6 x left skip over any x's and
q6 . q7 . left go back to 2nd .
q7 a q7 a left skip over any a's and go
q7 x q1 x right back to last x in 2nd section
q8 x q8 x right skip over any x's in 3rd part
q8 # halt-acc # same if no more b's then #a = 3*#b
由于您的其他问题已关闭，这里有一个答案。
这是我们的策略：
尝试划掉三个 a。如果我们成功了，划掉一个 b，然后重复这个过程。如果我们在上述任一方面都失败了，请确保不再有 b - 如果没有，停止接受，否则停止拒绝。
示例：
aabaaaba => xxbxaaba => xxxxaaba => xxxxxxbx => xxxxxxxx => halt-accept
aa => xx => halt-accept
aaa => xxx => halt-accept
状态可能如下所示：
state tape state' tape' direction comments
q0 a q1 x right read the 1st of 3 a's
q0 b q0 b right skip any b's
q0 x q0 x right skip any crossed-off
q0 # q6 # left if no a's make sure no b's
q1 a q2 x right read the 2nd of 3 a's
q1 b q1 b right skip any b's
q1 x q1 x right skip any crossed-off
q1 # q6 # left if just one a make sure no b's
q2 a q3 x left read the 3rd of 3 a's
q2 b q2 b right skip any b's
q2 x q2 x right skip any crossed-off
q2 # q6 # left if just two a's make sure no b's
q3 a q3 a left rewind to the front of the
q3 b q3 b left tape, skipping all a's, b's
q3 x q3 x left and x's until we get to the
q3 # q4 # right blank at the front
q4 a q4 a right skip any a's
q4 b q5 x left cross off one b
q4 x q4 x right skip any x's
q4 # halt-acc # same accept if no more b's found
q5 a q5 a left rewind the tape, skipping any
q5 b q5 b left a's, b's and x's until we get
q5 x q5 x left to the blank at the front of
q5 # q0 # right the tape; then repeat from q0
q6 a q6 a left just verify no more b's on
q6 b halt-rej b same the tape; we're starting at
q6 x q6 x left the end so scan backwards
q6 # halt-acc # same
我在研究图灵机， 然后我遇到了一些问题。
a^m . a^3n . b^n
如何给本机设计状态图？ 你能帮忙吗？
假设 m 和 n 之间没有关系，策略如下：
验证第一个周期之前的所有内容都是
a。如果您在进入第一期之前看到任何其他内容，请停止拒绝。除非假定m > 0，否则将句号视为第一个输入符号是可以的。如果您看到第二部分没有剩余的
a，请确认第三部分中没有剩余的b，如果是，则停止接受。否则，如果还有bs 剩余，halt-reject.如果第二部分还剩下
a，请划掉其中三个a。如果没有至少三个a要划掉，则暂停拒绝。如果有，那就划掉一个b。如果没有剩余的b可以划掉，则暂停拒绝。如果有b，请返回第 2 部分并继续第 2 步，直到您停止接受或停止拒绝。
示例：
aa.aaaaaa.bb => aa.xxxaaa.xb => aa.xxxxxx.xx => halt-accept
aa.aaaaa.bb => aa.xxxaa.xb => halt-reject
aa.aaaaaa.bbb => aa.xxxaaa.xbb => aa.xxxxxx.xxb => halt-reject
aa.aaaaaa.b => aa.xxxaaa.x => aa.xxxxxx.x => halt-reject
ba.aaaaaa.bb => halt-reject
这些州可能看起来像这样：
state tape state' tape' direction comment
q0 a q0 a right read a's until you see
q0 . q1 . right a period, crash otherwise
q1 a q2 x right if you see a's, cross off
q1 x q1 x right the 1st of 3. skip x's and
q1 . q8 . right if you see . check for no b's
q2 a q3 x right read the 2nd of 3 a's
q3 a q4 x right read the 3rd of 3 a's
q4 a q4 a right skip over any remaining a's
q4 . q5 . right to get to the 2nd .
q5 b q6 x left cross off one b for the 3 a's
q5 x q5 x right skip over any x's
q6 x q6 x left skip over any x's and
q6 . q7 . left go back to 2nd .
q7 a q7 a left skip over any a's and go
q7 x q1 x right back to last x in 2nd section
q8 x q8 x right skip over any x's in 3rd part
q8 # halt-acc # same if no more b's then #a = 3*#b
由于您的其他问题已关闭，这里有一个答案。
这是我们的策略：
尝试划掉三个 a。如果我们成功了，划掉一个 b，然后重复这个过程。如果我们在上述任一方面都失败了，请确保不再有 b - 如果没有，停止接受，否则停止拒绝。
示例：
aabaaaba => xxbxaaba => xxxxaaba => xxxxxxbx => xxxxxxxx => halt-accept
aa => xx => halt-accept
aaa => xxx => halt-accept
状态可能如下所示：
state tape state' tape' direction comments
q0 a q1 x right read the 1st of 3 a's
q0 b q0 b right skip any b's
q0 x q0 x right skip any crossed-off
q0 # q6 # left if no a's make sure no b's
q1 a q2 x right read the 2nd of 3 a's
q1 b q1 b right skip any b's
q1 x q1 x right skip any crossed-off
q1 # q6 # left if just one a make sure no b's
q2 a q3 x left read the 3rd of 3 a's
q2 b q2 b right skip any b's
q2 x q2 x right skip any crossed-off
q2 # q6 # left if just two a's make sure no b's
q3 a q3 a left rewind to the front of the
q3 b q3 b left tape, skipping all a's, b's
q3 x q3 x left and x's until we get to the
q3 # q4 # right blank at the front
q4 a q4 a right skip any a's
q4 b q5 x left cross off one b
q4 x q4 x right skip any x's
q4 # halt-acc # same accept if no more b's found
q5 a q5 a left rewind the tape, skipping any
q5 b q5 b left a's, b's and x's until we get
q5 x q5 x left to the blank at the front of
q5 # q0 # right the tape; then repeat from q0
q6 a q6 a left just verify no more b's on
q6 b halt-rej b same the tape; we're starting at
q6 x q6 x left the end so scan backwards
q6 # halt-acc # same