Description

This is the final programming assignment. Use a Visual C++ Win32 Console Application project.  You may also use C# .NET, however we will use C++ in class.

For this assignment, your program should read in a Turing machine, followed by one or more strings.  Your program should run each of the input strings through the machine and accept if the machine successfully halts.  Note that your program should trap for missing transitions and reject the string if no valid transitions are defined by the machine.

The input is provided by a text file, read through stdin by your program.  The format of the input file is as follows:

comment

number of transitions

current state, current symbol, new symbol, move, next state

…

strings

Starting at the “current state”, if the symbol under the R/W head matches the transition’s “current symbol”, it should be replaced with the “new symbol”.  The R/W head should then move left or right (L/R) as specified by the “move”, and the machine should transition to the “next state”.  If the next state is ‘H’ (halt), then the machine should end execution and accept the string.  The machine will start in state ‘1’ at the left most letter of the input string.

Note that the symbols on the tape are not limited to simply ‘a’ or ‘b’.  The strings will initially contain only a’s and b’s, but may be overridden by other symbols (e.g. ‘#’, or ‘1’).  Blank spots on the tape will be indicated by ‘_’ (underscore).

The tape is “infinite” in both directions.  This means your machine will need to have the ability to move left from the starting position.

Hint:  There are several possible ways to implement a bi-directional tape.  The most efficient will be to use two strings, one representing the tape to the right of the starting position, and the other representing the tape to the left of the starting position.  A single variable, representing the current tape position, can be used to index into either string, where negative positions are interpreted as indexing the left side string.

Example input file:

‘Ends in a

5

1, a, a, R, 2

1, b, b, R, 1

2, a, a, R, 2

2, b, b, R, 1

2, _, _, L, H

aba

bbaabba

bbabab

aaaab

b

a

Expected output for the example input file:

accept    aba

–>       aba

accept    bbaabba

–>       bbaabba

reject    bbabab

–>       bbabab

reject    aaaab

–>       aaaab

reject    b

–>       b

accept    a

–>       a

“accept” is printed only if the string reaches the Halt state ‘H’.  “reject” is printed if a transition cannot be found to meet a condition and the machine crashes.  After accept/reject, print a tab and then the input string.  On the next line, print an arrow “–>”, a tab, and then the content of the tape at the time the machine stops, not including any trailing blanks ‘_’.

Turn in your source code by removing the bin and obj directories and then zipping the folder containing the solution and all sub-folders.  Name the file CST229_Assign4_your_name.zip, where “your_name” is really YOUR NAME.  For example, I would name my zip file “CST229_Assign4_pete_myers.zip”.  Submit your zip file on Canvas to turn in your assignment.

Hints

Printing out the contents of the tap after accepting or rejecting a string is tricky. Leading/Trailing underscore characers should not be printed, and the tape is meant to be two-way infinite.  Here is a sample implementation that takes a brute force approach.  It assumes that there are two strings, leftContents and rightContents, where leftContents contains characters to the left of the starting position, starting with index 1 and going farther to the left as the index grows, and where rightContents contains the character at the starting position, index 0, and going farther to the right as the index grows.

Remember to use the code below to learn and then implement your own way to print the final tape contents.

std::string Tape::ToString()

{

unsigned int i;

std::string result = “”;

// copy in the leftContents (not including the 0th unused character)

// skipping any leading blanks ‘_’

for (i = leftContents.length() – 1; i > 0 && leftContents[i] == ‘_’; i–);

for (; i > 0 ; i–)

result += leftContents[i];

// find where the rightContents ends, before trailing blanks ‘_’

unsigned int last = rightContents.find_last_not_of(‘_’);

if (last != -1)

{

// copy in the rightContents

for (i = 0; i <= last; i++)

result += rightContents[i];

}

return result;

}