Машина Тьюринга для приема строки из трехсимвольного алфавита

Машины Тьюринга могут читать и записывать на ленту и перемещаться по ней вперед и назад. Если бы у вас была линия из трех цветных шариков, как бы вы увидели, что они расположены как струны в вашем языке? Вы можете проверить, что они в порядке, а затем отдельно посчитать каждый цвет и убедиться, что отношения сохраняются. «больше или равно» — это бинарное отношение, поэтому вы, вероятно, будете проверять обе пары по отдельности. Это действительно легко представить, используя три дополнительных ленты:

1. просканируйте слева направо, чтобы убедиться, что сначала идет a, затем b, затем c, затем вернитесь к началу
2. сканируйте вправо, считая буквы «а», записывая одну букву «а» на дополнительную ленту № 1 за каждую букву «а», которую вы читаете на входной ленте.
3. продолжайте сканирование, используя дополнительную ленту № 2, чтобы считать b
4. продолжайте сканирование, используя дополнительную ленту №3, чтобы считать c
5. сброс всех ленточных головок
6. отсканируйте вправо, чтобы убедиться, что на дополнительной ленте № 1 больше материала, чем на дополнительной ленте № 2.
7. сброс всех ленточных головок
8. отсканируйте вправо, чтобы убедиться, что на дополнительной ленте № 2 больше материала, чем на дополнительной ленте № 3.

Если мы не хотим использовать дополнительные ленты, как мы можем действовать дальше? Что ж, мы можем пойти дальше и сначала убедиться, что символы расположены в правильном порядке... остальное будет аккуратнее. Затем мы можем «вычеркивать» пары a и b до тех пор, пока не будут исчерпаны все b (если мы сначала исчерпаем все a, затем 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