Есть много правильных способов сделать это. Я просто пройдусь по одному из них, надеюсь, продемонстрирует полезный способ решения этих проблем.
Во-первых, мы замечаем общность n между тремя сегментами. Мы вычеркнем символы из каждого раздела, по одному, чтобы убедиться, что они имеют правильные отношения. Во-первых, мы можем убедиться, что отношения между a и b правильные. Затем мы можем проверить отношения между a и c. Если они оба правы, мы закончили.
Во-первых, давайте избавимся от надоедливого "+1" от a. Это означает, что у нас есть по крайней мере один a независимо от того, что n. Итак, мы можем начать с изменения a на X. Теперь оставшиеся входные данные должны иметь n экземпляров a, 2n экземпляров b и 3n экземпляров c. Если у нас нет одного a, мы можем немедленно остановить-отклонить; у нас не может быть 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