Programming Homework Assignment P-2
Due 12:45 PM, Thursday, April 13, 2006
________________________________________________________________________
Programming Language Choice
________________________________________________________________________
The program can be written in Java, C++ or C. You must follow
good software design practices, and in particular use adequate data
abstraction. Thus I recommend Java or C++. If you use a non-object-
oriented language, you can still use data abstraction (for instance,
you can make typedefs in C that mimic classes and organize your
functions to mimic class methods).
Your program MUST compile on the CS department's machines. So do not
use any non-standard libraries. If you are in doubt, please check with
Mu-Fen -- she is the one who will be compiling and checking your program.
________________________________________________________________________
Program Specification
________________________________________________________________________
You are to write a program that simulates the behavior of a nondeterministic
Turing machine (NTM).
The program will first prompt the user for
the name of a file that describes the NTM's state transition diagram
(see below for the specification of this file).
Then it will prompt the user for an input string
and will proceed to simulate all the computations of the NTM on
that input.
If the NTM accepts the string, your program must eventually print
out "accepted"; otherwise, your program will be in an infinite loop.
Input Requirements:
-------------------
* input file: description of the state transition diagram of a
nondeterministic Turing machine.
line 1: integer
number of states. They will be numbered from 0 to n-1, where
n is the value of line 1. State 0 will be the start state.
line 2: integer1 integer2 integer3 ...
list of final (accepting) states, separated by blanks
lines 3...: integer1 char1 integer2 char2 dir
transition (integer1, char1) -> (integer2, char2, dir), where
integer1 is current state, char1 is current tape symbol,
integer2 is new state, char2 is new tape symbole, and dir
is either L or R.
Assumptions:
* Sigma, the input alphabet, is {a,...z,0,...9}.
* Gamma, the tape alphabet, is Sigma U {A,...,Z} U {@}, where
@ represents the blank character.
YOU MUST FOLLOW THIS FORMAT! Your program will be tested on OUR
input files, which will conform to this format.
For example, the NTM of Exercise 8.4.2 would be represented like this
(replacing B with @):
3 // there are 3 states, 0, 1, 2, and 0 is the start state
2 // state 2 is the only accepting state
0 0 0 1 R // if in state 0 reading 0, stay in state 0, write 1, move R
1 0 1 0 R // if in state 1 reading 0, stay in state 1, write 0, move R
1 0 0 0 L // if in state 1 reading 0, go to state 0, write 0, move L
0 1 1 0 R
1 1 1 1 R
1 1 0 1 L
1 @ 2 @ R
Note that there are two choices for what to do if you are in state 1
reading 0, and two choices for what to do if you are in state 1 reading 1.
Output requirements:
--------------------
(*updated 4/12/06*).
Your program must print out the sequence of instantaneous descriptions
(i.d.'s) that the simulation calculates.
You have some flexibility in how to format the output, but
you need to list the computations in a logical order, indicate
which nondeterministic choices were made at each stop, and whether
the computation is accepting or not.
For example, if 010 is the input
to the NTM in Exercise 8.4.1, and if the transitions are numbered like this:
0 0 0 1 R (1)
0 0 0 1 R (2)
1 0 1 0 R (1)
1 0 0 0 L (2)
0 1 1 0 R (1)
0 1 1 0 R (2)
1 1 1 1 R (1)
1 1 0 1 L (2)
1 @ 2 @ R (1)
1 @ 2 @ R (2)
then a sample output would be
length 0 computation:
[q0]010
length 1 computations:
1: [q0]010
1[q0]10
2: [q0]010
1[q0]10
length 2 computations;
11: [q0]010
1[q0]10
10[q1]0
12: [q0]010
1[q0]10
10[q1]0
21: [q0]010
1[q0]10
10[q1]0
22: [q0]010
1[q0]10
10[q1]0
and keep continuing at least until length 4 computations (where
acceptance occurs).
Implementation Requirements:
----------------------------
Use the following algorithm.
(1) Determine the maximum number of choices in the transition function
for each (state,symbol) pair. Call this number m (m=2 in the example).
"Pad" out the transition function so that each (state,symbol) pair
has exactly m choices (repeat one of the choices, if necessary), labeled
1 to m.
(2) Then systematically simulate all the computations of the input Turing
machine on the input string in this fashion:
Each computation can be described as a sequence of integers between 1 and m,
indicating which choice for the current (state,symbol) pair is taken
to determine the new state, new tape symbol, and movement direction.
The computations will be considered in lexicographic order, in increasing
order of length, as explained in lecture on March 23.
Don't forget that you have to simulate the tape!
(3) If your program ever runs across a computation that halts (i.e.,
reaches a (state,symbol) pair for which there is no next step) in an
accepting state, then it should output "accept" and halt.
________________________________________________________________________
Grading Scheme:
________________________________________________________________________
This assignment is worth 50 points total:
15 points correctness
15 points design
10 points testing
10 points documentation
Design Requirements:
--------------------
Use principles of good design! Use data abstraction appropriately.
The output format will be graded as part of this.
Testing Requirements:
--------------------
You must turn in a testing plan. This is a *typed* document that
explains what test cases you used and *why*. Explain why the test
cases you have picked should give high confidence in the correctness
of your program.
You must also turn in the output of your test cases.
Documentation Requirements:
--------------------------
Your source code must be properly documented. I assume that you know
what that means. If you are unsure, refer to material from your
previous programming courses, or see the professor or the TA.
At a minimum it includes giving mnemonic names to your variables,
documenting what each function/method does in terms of its input
and output, and giving a high level overview of the program as a
whole.
________________________________________________________________________
What to Turn In and How
________________________________________________________________________
You will turn in one .tar.gz or .zip file using the CS Department's turnin
facility (http://helpdesk.cs.tamu.edu/docs/csnet_turnin).
Your file must be named .tar.gz or .zip,
e.g., smith.zip.
Your tar (or zip) file must contain the following files:
* documented source files for your program, ready to be compiled
* inputs and outputs for your test cases as text files.
Be sure to name them TC-1-in, TC-1-out, TC-2-in, TC-2-out, ...,
where TC-i-in and TC-i-out are the inputs and outputs respectively
for your i-th test case.
* a README file giving the commands needed to compile and run your
program. If there are a lot of files, include a makefile.