more than one executable for this project.
Eachof the exercises below requires that the program read and execute a text file that contains the initial string for the Turing machine tape, AND the state machine for that exercise. Hence the deliverables for this project are:
1) the project design;
2)
one project5.cpp file
that is to be used for ALL the exercises below; and,
3)
one input text file for each exercise below.
Write a Turing machine to accomplish each of the following exercises. Use your project5 executable to simulate the Turing machine’s behavior. You must submit a sample text file for each exercise containing a sample input string for the tape, and a set of state machine transitions appropriate to that exercise.
As the Turing machine tape cannot be of infinite length, it is suggested that you limit the tape to 100 characters. The constants and the state transition structure could be:
const char BLANK = 'B';
const char ZERO = '0';
const char ONE = '1';
const char STAR = '*';
const char LEFT = ‘L’;
const char RIGHT = ‘R’;
const int MAXTAPE = 100;
const int MAXSTATES = 25;
const short STARTPOS = 40;
const char STARTSTATE = ZERO;
struct stateTrans {
char state;
char readChar;
char nextState;
char writeChar;
char move;
};
Note that the start position for the input file provided initial string is in the MIDDLE of the tape, and that the entire tape is first to be initialized to all blanks (all ‘B’).
Input and output should conform to the following. One example used in the lectures was a Turing machine that validated any string with all 1s, and rejected any string that had at least one 0. The example input file (with an initial string of 5 1s) was:
11111
0101R
0B1BL
1111L
1B2BR
0030L
3141R
3B4BR
The output for this Turing machine simulation should print out the starting data as:
Tape starts at 40 length = 5 highlights position 40 tape =
B |1| XXXXXXXXXXB
XXXXXXXXXXR
0 B 1 B L
XXXXXXXXXXL
1 B 2 B R
XXXXXXXXXXL
XXXXXXXXXXR
3 B 4 B R
Note that the initial string is shown flanked by Bs, and the starting position (40) is highlighted inside two vertical bars. The length of the initial string is also indicated.
At the end of the run the output should be:
Execution halts in state 2
Tape starts at 40 length = 5 highlights position 40 tape =
B |1| XXXXXXXXXXB
Note that the read/write head is left at the beginning of the validated string when successful.
If we start instead with the input file:
11101
0101R
0B1BL
1111L
1B2BR
0030L
3141R
3B4BR
this changes the initial string to contain a 0, and the initial and final output should be:
Tape starts at 40 length = 5 highlights position 40 on tape =
B |1| XXXXXXXXXXB
XXXXXXXXXXR
0 B 1 B L
XXXXXXXXXXL
1 B 2 B R
XXXXXXXXXXL
XXXXXXXXXXR
3 B 4 B R
. . .
Execution halts in state 4
Tape starts at 40 length = 5 highlights position 43 on tape =
B 1 1 1 |0| 1 B
Note that the read/write head is left pointing to the invalid 0 embedded in the string.
You MAY want to add a verbose option to help you with debugging (see Project 3, above).
Project 5 Exercises:
1) Create a Turing machine that validates all strings of alternating 0s and 1s; all of the following should be validated by the Turing machine:
Valid Strings
|
0
|
1
|
01
|
10
|
010
|
101
|
0101
|
1010
|
01010
|
10101
|
...
|
The string: 01001 should not be validated by the Turing machine. Note the regular expression to be validated (using symbolism explained in Week 13) is:
(01)* | (10)* | (01)*0 | (10)*1
2) Create a Turing machine to subtract two positive numbers in unary 1s format. Require that the second number be less than the first (so there are no negative results). In unary 1s format represent n as n+1 1s, m as m+1 1s, and the result n-m as (n-m)+1 1s. Example: 5 is to be represented as 111111, 2 is to be represented as 111, and 5-2, or 3, is to be represented as 1111. Be sure to verify that n – n is 0 (or a single 1 in unary 1s format).
3) Create a Turing machine to find the 2s complement of an 8-bit
binary number
(do NOT use unary 1s representation). See also Assignment 6, above. For example: find the 2s complement of: XXXXXXXXXX, as an 8-bit binary number. First find the 1s complement (flipping all the 0s and 1s), which is: XXXXXXXXXX, and then add 1 to the result:
XXXXXXXXXX
+ 1 =
XXXXXXXXXX
Be careful to correctly handle any carry operations when adding 1 to the result!
Note that the sum of the original 8-bit number and its 2s complement (which is the negative of the original 8-bit number) is the 8-bit number: XXXXXXXXXX.
XXXXXXXXXX +
XXXXXXXXXX =
XXXXXXXXXX
with a carry of 1 out of the most significant bit of the result.
Be sure to verify that your Turing machine correctly determines that:
XXXXXXXXXXis the 2s complement of
|
XXXXXXXXXXis the 2s complement of
|
XXXXXXXXXXis the 2s complement of
|