Representation of a Turing Machine that Recognizes the Language of n a's followed by n b's

   
 In this picture the ovals again represent control states of the machine and the arrows represent transitions between control states. However, since the Turing Machine may move R, L, or Write to the tape, the action is represented explicitly in the diagram. On each arrow is the tape element followed by the '/' and then the action. For example, the transition from da to srb represents the tuple "da a # srb"; that is if you are in control state "da" and you are reading an "a" on the tape, then overwrite a with # (i.e. erase it) and make srb the current control state.
Below is an animation showing the tape contents as the machine above processes the input #aabb#.
     
     

Machines
Computational Approach
© Charles F. Schmidt