如何从字母表创建一台机器

How to create a machine from alpabet

我在研究图灵机, 然后我遇到了一些问题。

a^m . a^3n . b^n

如何给本机设计状态图? 你能帮忙吗?

假设 m 和 n 之间没有关系,策略如下:

  1. 验证第一个周期之前的所有内容都是 a。如果您在进入第一期之前看到任何其他内容,请停止拒绝。除非假定 m > 0,否则将句号视为第一个输入符号是可以的。

  2. 如果您看到第二部分没有剩余的 a,请确认第三部分中没有剩余的 b,如果是,则停止接受。否则,如果还有 bs 剩余,halt-reject.

  3. 如果第二部分还剩下 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