Разработайте машину Тьюринга, которая принимает язык L= {a^2 b^2n: n›=1}

Если ваш язык a^2 b^2n = {aabb, aabbbb, aabbbbbb, ...}, то это обычный язык, и ПП для него сначала читает два a, затем два b, затем либо пробел, либо два дополнительных b за раз, пока не будет найден пробел.

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, ...}, этот язык не зависит от контекста, и НП для него вычеркивает соответствующие 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