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.
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
Last
Updated 01/05/2004
© L.Heath,
2000
Modified by J.A.N. Lee, 2004