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
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000