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

Есть много правильных способов сделать это. Я просто пройдусь по одному из них, надеюсь, он проиллюстрирует полезный способ решения этих проблем.

Во-первых, мы замечаем общность n между тремя сегментами. Мы будем вычеркивать символы из каждого раздела по одному, чтобы убедиться, что они имеют правильные отношения. Во-первых, мы можем проверить правильность соотношения между a и b. Затем мы можем проверить связь между a и c. Если они оба верны, мы закончили.

Во-первых, давайте избавимся от надоедливого "+1" из a. Это означает, что у нас есть по крайней мере один a независимо от того, что такое n. Итак, мы можем начать с замены a на X. Теперь оставшиеся входные данные должны содержать n экземпляров a, 2n экземпляров b и 3n экземпляров c. Если у нас нет одного а, мы можем немедленно остановиться-отклонить; у нас не может быть n+1 экземпляров a, если у нас нет хотя бы одного.

Теперь, если имеется больше экземпляров a, вычеркните его, написав вместо него A, и вычеркните два экземпляра b, написав на их месте B. Затем вернитесь и ищите другие экземпляры a, прыгая туда-сюда, пока не останется больше экземпляров a. Затем проверьте, что больше нет экземпляров b; если это так, то экземпляров b было в два раза больше, чем экземпляров a, и первые два раздела имеют правильные отношения. Если в какой-то момент у вас не хватило b, чтобы вычеркнуть его, или если после того, как у вас закончилось a, у вас все еще было b, то вы можете безопасно остановиться и отклонить на этом этапе.

Затем вы можете сделать то же самое для экземпляров A и c, просто вычеркнув три экземпляра c вместо двух. Если мы обнаружим, что A истощается одновременно с c, мы закончили и прекращаем принимать.

Переходы могут выглядеть так:

Q    T    Q'    T'    d        comment
q0   a    q1    X     right    account for +1

q1   a    q2    A     right    n>0 case, continue
q1   #    hA    #     same     n=0 case, accept

q2   a    q2    a     right    skip uncrossed a
q2   B    q2    B     right    skip crossed b
q2   b    q3    B     right    find first uncrossed b, cross it

q3   b    q4    B     left     find next b, cross it

q4   B    q4    B     left     find last uncrossed a
q4   a    q2    A     right    cross it
q4   A    q4    A     left     skip crossed a, if any
q4   X    q5    X     right    ran out of a to cross

q5   A    q5    A     right    skip crossed a
q5   B    q5    B     right    skip crossed b
q5   c    q6    c     left     verify existence of some c

q6   C    q6    C     left     skip crossed c
q6   B    q6    B     left     skip crossed b
q6   A    q7    a     right    find last crossed a, uncross
q6   X    q10   X     right    ran out of crossed a

q7   a    q7    a     right    skip uncrossed a
q7   B    q7    B     right    skip crossed b
q7   C    q7    C     right    skip crossed c
q7   c    q8    C     right    find first uncrossed c, cross
q8   c    q9    C     right    cross 2nd uncrossed c
q9   c    q6    C     left     cross 3rd uncrossed c

q10  a    q10   a     right    skip uncrossed a
q10  B    q10   B     right    skip crossed b
q10  C    q10   C     right    skip crossed c
q10  #    hA    #     same     accept if no leftover symbols until end

Поскольку мы не должны решать вашу домашнюю работу :), я решил следующий язык на JFLAP, и вы можете немного изменить его для своего языка. Логика та же, и вам нужно добавить пару состояний. L = {a ^ n + 1 b ^ 2n : n >= 0}