A Multi-State Example 

The tape alphabet is {b, 0, 1}.

The set of states is {A, B, C}.

The instructions are:

       

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)

 

Where b stands for the "blank" character.
The starting state is A and the tape is positioned so that the rightmost symbol is under the read/write head.



We try this on the input

10001

What does it do?

 

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)
Start
 
1
0
0
0
1
       
A
       
 
1
0
0
0
       
 
C
       
   
1
0
0
1
       
   
B
       
     
1
0
0
1
     
     
B
     
       
1
0
0
1
   
       
B
   
         
 
0
0
0
1
 
HALT
         
C
 

 

How about:

10000?

 

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)
Start
 
1
0
0
0
0
       
A
       
 
1
0
0
0
       
 
B
       
   
1
0
0
0
       
   
B
       
     
1
0
0
0
     
     
B
     
       
1
0
0
0
   
       
B
   
         
 
0
0
0
0
 
HALT
         
C
 

 

Try 10101

 


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000