Разработайте машину Тьюринга, которая принимает язык 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, ...}, язык регулярный и ТМ для него сначала читает два aс, то два 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, ...}, язык не зависит от контекста, и ТМ для него не соответствует aaс и bbпока у вас не закончатся символы.

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