Search code examples
discrete-mathematicsturing-machines

Turing Machine to Accept String from a 3 character alphabet

I need to create a turing machine that accepts the language a^1 b^j c^k where i >= j >= k, but I am not even really sure how to start. Turing machines in this context are a hard concept for me to grasp for some reason.

Solution

  • Turing machines can read and write to the tape and move back and forth over it. If you had a line of three colors of marbles how would you see if they arranged like the strings in your language? You could verify they're in order and then separately count each color and make sure the relationships hold. "greater than or equal to" is a binary relation so you'd probably check both pairs separately. This is really easy to envision using three extra tapes:

    1. scan from left to right to make sure a comes first, then b, then c, then go back to the beginning
    2. scan right counting the a's, writing one a to extra tape #1 for each a you read on the input tape
    3. continue scanning using extra tape #2 to count b
    4. continue scanning using extra tape #3 to count c
    5. reset all tape heads
    6. scan right to make sure extra tape #1 has more stuff in it than extra tape #2
    7. reset all tape heads
    8. scan right to make sure extra tape #2 has more stuff in it than extra tape #3

    If we don't want to use extra tapes, how can we proceed? Well, we can go ahead and make sure the symbols are in the right order first... makes the rest neater. Then, we can "cross off" pairs of a and b until all b are exhausted (if we exhaust all a first, then halt_reject); then, un-cross the b and cross off pairs of b and c until you run out of c (if you run out of b first, halt_reject). Something like...

     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   //

    Example 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