This project is to be done as a group project (see the GroupProjects file on Canvas for group assignments). Design a program that simulates a Turing machine, project5.cpp; there should be no more than one executable for this project. Each of 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:

2)one project5.cpp file that is to be used for ALL the exercises below; and,

3)one input text for each exercise below.

Write a Turing machine to accomplish each of the following exercises. Use your project5 executable to simulate the Turing machines 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| 1 1 1 1 B

0 1 0 1 R

0 B 1 B L

1 1 1 1 L

1 B 2 B R

0 0 3 0 L

3 1 4 1 R

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| 1 1 1 1 B

Note that the read/write head is left at the beginning of the validated string.

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 tape =

B |1| 1 1 0 1 B

0 1 0 1 R

0 B 1 B L

1 1 1 1 L

1 B 2 B R

0 0 3 0 L

3 1 4 1 R

3 B 4 B R

. . .

Execution halts in state 4

Tape starts at 40 length = 5 highlights position 43 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 the next block) 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, below. For example: find the 2s complement of: 00010111, as an 8-bit binary number. First find the 1s complement, which is: 11101000, and then add 1 to the result:

11101000

+ 1 =

11101001

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 00000000.

00010111 +

11101001 =

00000000

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:

0000 0000 is the 2s complement of	0000 0000
1111 1111 is the 2s complement of	0000 0001
0000 0001 is the 2s complement of	1111 1111