Computer Science 332

Theory of Computation

Programming Assignment #3

A Deterministic Finite Automaton Simulator

due Friday, October 1, 2004 by noon

                In this assignment, you are to write a program that takes a DFA 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 present and in the correct format.  After reading this file, it will proceed in the same manner as the first two programs.  A sample run is shown below (user input is underlined.)

Machine file? DFA.txt
Word? aba
The machine accepts "aba".
Word? bab
The machine does NOT accept "bab".
Word? END

(As implied above, the String "END" is used to terminate the loop.)

                Your DFA will work on a “K” letter alphabet where the letters used are the first K letters of the Roman alphabet.  Thus, if K = 2, then the alphabet is “a” and “b”.  You may assume that all user input consists only of valid letters in the alphabet (other than the “end” case).

                As before, you are to write your program in Java.  You will, of course, need to make use of the String class, but you may not use any member functions that get/search entire substrings.  Other than for purposes of input and output, you must consider only individual characters of the string.   

                The file format is as follows:

                We make the following assumptions: (1) that states are numbered starting at 0, (2) that the start state is numbered 0, (3) that the transitions are given in alphabetical order, and (4) that all states are shown (i.e. that there is no implicit death state).

                The following file would describe a machine equivalent to M₄ in the text (see page 38) [I numbered the states starting from the top.]

   You are to mail the appropriate source file(s) to me (at dlevine@cs.sbu.edu) such that I receive it by noon on Friday, October 1.

      The class containing your main method is to be named DFA.  Any variation from this name will result in a deduction.  Likewise, your messages are to be exactly as specified in the sample run.  There is a single space following each of the question marks; be sure to include that space.  This is important as the assignment may be graded electronically!

               For those of you who don't feel comfortable with the I/O issues, here is a program that prompts the user for a data file and sums all of the numbers within that file.  Here is one of the data files that I used to test it.

                IN ADDITION, as a double check that you understand the file format, you are to submit (either on paper or electronically) the file describing the machine used in Exercise 1.16 (b) on page 86.  This submission must be received by me by 8 a.m. on Friday September 24.  [Note that you will need to subtract one from all of the state numbers to be consistent with our file format.]