Computer
Science 332
due Friday, November 17, 2000 by 4 p.m.
In this assignment, you are to write a program that takes a Turing Machine, and associated tape, as input (from a file) and then simulates its behavior on various inputs (taken from the keyboard).
Your program should begin by prompting for the file name and then reading a data file in the format described below. You may assume that all data files are in the correct format. Once the machine halts, you should print the tape and a note indicating the position of the tape head. You may assume that the machine will eventually halt.
Your Turing Machine will work on a three letter alphabet { 1, x, # } where # will be used instead of the book’s “blank” symbol. As before, you are to write your program in C++, and you may use the apstring class, but you may not use the substring member function. Other than for purposes of input and output, you must consider only individual characters of the string. You may also wish to make use of the apmatrix class, though this is not required. It is strongly recommended that you model this program after the one you wrote for program #3.
The file format is as follows:
<number of states from which you can leave> <number of transitions>
and an action is L (meaning “move the tape head left”) or R (meaning “move the tape head right”).
We make the following assumptions: (1) that states are numbered starting at 0, (2) that the start state is numbered 0, (3) the accepting state is numbered –1, and (4) the rejecting state is numbered –2.
For example, the “equality machine” given in class can be encoded as
5 13
0 1 1 # R
0 x 4 x R
1 1 1 1 R
1 x 2 x R
2 1 3 x L
2 x 2 x R
2 # -2 # R
3 x 3 x L
3 1 3 1 L
3 # 0 # R
4 # -1 # R
4 1 –2 1 R
4 x 4 x R
111x111
0
The output for this case would be to accept the string. As a double-check for correctness, have your machine print the tape when it is done.
You are to mail the appropriate .cpp file(s) to me (at dlevine@cs.sbu.edu) such that I receive it by 4 p.m on Friday, November 17.
IN ADDITION, as a double check that you understand the file format, you are to draw me a machine that accepts any string of x’s and 1’s that contains an even number of 1’s and show me the contents of a file that describes such a machine. This submission must be received by me by 8 a.m. on Monday, November 13.