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.