设计一个接受语言L = {a ^ 2 b ^ 2n：n> = 1}的图灵机

Question

我想设计一个接受语言L = {a ^ 2b ^ 2n：n> = 1}的图灵机：。正方形b平方（n）

Answer 1

如果你的语言是a^2 b^2n = {aabb, aabbbb, aabbbbbb, ...}，那么语言是常规的，并且它的TM首先读取两个as，然后是两个bs，然后一次空白或两个额外的bs，直到找到空白。

q    t    q'    t'    d
-----------------------
q0   a    q1    a     right    // read two a's from the
q1   a    q2    a     right    // beginning of the tape

q2   b    q3    b     right    // read at least two b's
q3   b    q4    b     right

q4   #    hA    #     left     // read more pairs of b's
q4   b    q3    b     right    // or halt if input is done

如果您的语言是a^2n b^2n = {aabb, aaaabbbb, aaaaaabbbbbb, ...}，那么该语言是无上下文的，并且TM for it会越过匹配的aas和bbs，直到您的符号用完为止。

q    t    q'    t'    d
-----------------------
q0   a    q1    #     right    // erase two a's from
q1   a    q2    #     right    // the front of the tape

q2   a    q2    a     right    // scan to the end
q2   b    q2    b     right    // of the tape
q2   #    q3    #     left

q3   b    q4    #     left     // erase two b's from
q4   b    q5    #     left     // the end of the tape

q5   a    q5    a     left     // scan to the beginning
q5   b    q5    b     left     // of the tape
q5   #    q6    #     right

q6   a    q1    a     right    // try to start erasing a's
q6   #    hA    #     -        // or halt if all input is erased