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

Question

我想设计一个接受语言 L= {a^2b^2n: n>=1} 的图灵机：。a 方 b 方 (n)

Answer 1

如果您的语言是a^2 b^2n = {aabb, aabbbb, aabbbbbb, ...}，则该语言是常规语言，并且它的 TM 首先读取两个as，然后读取两个 s，然后一次读取b空白或两个附加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 会交叉匹配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