Машины Тьюринга могут читать и записывать на ленту и перемещаться по ней. Если бы у вас была линия из трех цветов мрамора, как бы вы увидели, если бы они располагались как строки на вашем языке? Вы можете проверить, что они в порядке, а затем отдельно подсчитать каждый цвет и убедиться, что отношения сохраняются. «больше или равно» - это бинарное отношение, поэтому вы, вероятно, проверяете обе пары отдельно. Это действительно легко представить, используя три дополнительные ленты:
- Сканирование слева направо, чтобы убедиться, что сначала идет a, затем b, затем c, затем вернитесь к началу
- сканировать правильно, считая a, записывая одно a на дополнительную ленту # 1 для каждого a, который вы читаете на входной ленте
- продолжить сканирование с использованием дополнительной ленты # 2 для подсчета b
- продолжить сканирование с использованием дополнительной ленты # 3 для подсчета c
- сбросить все магнитные головки
- сканируйте вправо, чтобы убедиться, что на дополнительной ленте № 1 содержится больше материала, чем на дополнительной ленте № 2
- сбросить все магнитные головки
- сканируйте вправо, чтобы убедиться, что на дополнительной ленте №2 содержится больше материала, чем на дополнительной ленте №3
Если мы не хотим использовать дополнительные ленты, как мы можем продолжить? Что ж, мы можем пойти дальше и убедиться, что символы находятся в правильном порядке в первую очередь ... делает остальные аккуратнее. Затем мы можем «вычеркнуть» пары a и b, пока все b не будут исчерпаны (если мы сначала исчерпали все, то halt_reject); затем открепите b и вычеркните пары b и c, пока не исчерпаете c (если сначала у вас закончится b, halt_reject). Что-то вроде ...
q t q' t' d
q0 # q1 # right //
q1 a q1 a right //
q1 b q2 b right //
q1 # q4 # left //
q2 b q2 b right // verify subset of
q2 c q3 c right // a*b*c*
q2 # q4 # left //
q3 c q3 c right //
q3 # q4 # left //
q4 a q4 a left //
q4 b q4 b left // reset input
q4 c q4 c left // tape to start
q4 # q5 # right //
q5 a q5 a right //
q5 A q5 A right // change susbtring a^j b^j
q5 b q6 B left // into substring A^j b^j
q5 B q5 B right // if run out of a, crash
q5 c q7 C left // if run out of b and no c, accept
q5 # h_a # left // if run out of b and c, continue
q6 a q5 A right //
q6 A q6 A left //
q6 B q6 B left //
q7 B q8 D right //
q7 C q7 C left // change substring B^k c^k
q7 D q7 D left // to substring D^k c^k
q8 D q8 D right // if run out of B, crash
q8 C q8 C right // if run out of c, accept
q8 c q7 C left //
q8 # h_a # left //
Пример 1: aaabbc
(q0, [#]aaabbc#) -> (q1, #[a]aabbc#) -> (q1, #a[a]abbc#) //
-> (q1, #aa[a]bbc#) -> (q1, #aaa[b]bc#) -> (q2, #aaab[b]c#) // a*b*c*
-> (q2, #aaabb[c]#) -> (q3, #aaabbc[#]) -> (q4, #aaabb[c]#) //
-> (q4, #aaab[b]c#) -> (q4, #aaa[b]bc#) -> (q4, #aa[a]bbc#) //
-> (q4, #a[a]abbc#) -> (q4, #[a]aabbc#) -> (q4, [#]aaabbc#) // reset
-> (q5, #[a]aabbc#) //
-> (q5, #a[a]abbc#) -> (q5, #aa[a]bbc#) -> (q5, #aaa[b]bc#) //
-> (q6, #aa[a]Bbc#) -> (q5, #aaA[B]bc#) -> (q5, #aaAB[b]c#) // a^j b^j
-> (q6, #aaA[B]Bc#) -> (q6, #aa[A]BBc#) -> (q6, #a[a]ABBc#) // A^j B^j
-> (q5, #aA[A]BBc#) -> (q5, #aAA[B]Bc#) -> (q5, #aAAB[B]c#) //
-> (q5, #aAABB[c]#) -> (q7, #aAAB[B]C#) //
-> (q8, #aAABD[C]#) -> (q8, #aAABDC[#]) -> (ha, #aAABD[C]#) // B^k c^k
// D^k C^k