Programming Homework Assignment P-1 Due 12:45 PM, Tuesday, February 14, 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 deterministic finite automaton (DFA). The program will first prompt the user for the name of a file that describes the DFA's state transition diagram (see below for the specification of this file). Then it will go into a loop; in each iteration of the loop, it will prompt the user for an input string and will then print out a representation of the computation of the DFA on that input string and indication as to whether the string was accepted or rejected. I/O Requirements: ----------------- * input file: description of the state transition diagram of a finite automaton as a directed graph. 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 integer2 character transition from state integer1 to state integer2 labeled with character - use # to represent epsilon. YOU MUST FOLLOW THIS FORMAT! Your program will be tested on OUR input files, which will conform to this format. For example: 3 2 0 1 a 0 0 b 1 2 a represents the state transition diagram with three states, 0 through 2, state 0 is the start state, there is a self-loop on state 0 labeled b, there is a transition from state 0 to state 1 labeled a, and a transition from state 1 to state 2 labeled a. Finally, state 2 is the only accepting state. * output: for each input string, a nicely formatted and well-designed representation of the computation of the DFA on that string, together with an indication as to whether the string was accepted or rejected. ________________________________________________________________________ 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. You must represent the state transition diagram of the DFA as a graph. Be sure to have a graph class (or abstract data type equivalent). 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. ________________________________________________________________________ Extra Credit: ________________________________________________________________________ For 20 points extra credit, you can have your program handle nondeterministic finite automata. For each input string, you will need to output *every* computations of the NFA on that input, together with an indication as to whether that computation accepted or rejected, as well as indication as to whether the string is in the language of the NFA. ________________________________________________________________________ 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.