This turing machine accepts all strings of the form a^nb^nc^n Namely, all strings consisting of any number of a's, followed by the same number of b's, followed by the same number of c's. Method: 'Mark' the first 'a' on the string by replacing it with an 'x'. Then move to the right to mark a corresponding 'b', and then a corresponding 'c'. Then go back to the front of the string and repeat. Once the string consists of all x's, then we know the string is accepted. --------------------------------------------------------- State 4 is the final state. We can specify that any state that doesn't appear as an argument in the transition function (i.e., the first element of a quintuple) is to be a final state. State 0: find a first 'a' and mark it (0xx0R Move past x's at the string front (a's that were already marked). (0ax1R Mark the first 'a' we find, go to the right looking for a 'b' (0 4R If all we found were x's, then everything must have been marked off, so the string is accepted. Go to the final state and halt. State 1: we had found and marked an 'a'. Now look for a 'b'. (1aa1R (1xx1R Move past b's that were already marked (1bx2R Found a 'b'. Mark it, and go into state 2 State 2: We had found and marked a 'b' to go along with the 'a'. Now find a 'c'. (2bb2R (2xx2R (2cx3L Found a 'c'. Mark it and go into state 3. State 3: We have marked off an 'a', a 'b' and a 'c'. Now go back to the front of the string to repeat this. (3aa3L (3bb3L (3xx3L (3 0R Found the front of the string. Go back to state 0 to find a new 'a'.