Project 2

Due 11:59pm Tuesday, Mar 25th, 2008

Students can make a very late Project 2 submission until Thursday, March 27 11:59pm with a 20% penalty.

Introduction

You will need to implement a Finite Automata Interpreter that can build up NFAs, convert them to DFAs, minimize the DFAs, then test whether a string is accepted by the DFA.

Getting Started

Download the following archive file p2.tar and extract its contents using the command: tar xf p2.tar.

Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:

To test your FiniteAutomaton implementation, you can execute it on input files from the command line by typing commands like fa.rb < public_1.in. The fa.rb file you downloaded already implements many of the functionality of the Finite Automata Interpreter, such as the actual interpreter itself. All you need to do is implement most of the functionality of the FiniteAutomaton class. The interpreter will function by invoking methods of the FiniteAutomaton class. Like the Java bytecode interpreter, the finite automaton interpreter uses a stack to store its results. Operations will applied to operands popped off the stack. You can invoke the interpreter manually. The interpreter will accept the following commands:

symbol creates finite automaton that accepts the symbol (if the symbol is a lowercase letter), or empty string (if symbol is an uppercase E)
. pops off top 2 finite automaton on stack, creates a new NFA representing their concatenation, then pushes result back onto stack
| pops off top 2 finite automaton on stack, creates a new NFA representing their union, then pushes result back onto stack
* pops off top finite automaton on stack, creates a new NFA representing its closure, then pushes result back onto stack
SIZE prints # of states in the finite automaton at the top of the stack
PRINT prints the finite automaton at the top of the stack
DFA converts finite automaton (DFA or NFA) at the top of the stack to a DFA
MINIMIZE minimizes the finite automaton (must be a DFA) at the top of the stack
"str" decides whether finite automaton (must be a DFA) at the top of the stack accepts or rejects string str
GENSTR# prints all strings accepted by finite automaton (must be a DFA) at the top of the stack of length # or less
DONE interpreter exits

Part 1: Extend the FiniteAutomaton class to support NFAs

The FiniteAutomaton class you downloaded is based on the DFA class used as an example during discussion section. The original DFA class was able to represent DFAs and run them to determine whether input strings are accepted by the DFA. You need to decide how to change/extend the FiniteAutomaton class to represent both NFAs and DFAs. Remember this means your class should support features in NFAs not in DFAs, such as epsilon-transitions and multiple transitions with the same label. You may choose to represent epsilon-transitions as transitions labeled with the empty string "" or some other label. You do not need to implement the ability to run NFAs on input strings, but you should be able to run DFAs on input strings I.e., the accept? method should return true if the string would be accepted and false otherwise if your FiniteAutomaton object is actually a DFA.

Part 2: Building NFAs out of other NFAs

The symbol! method for creating a new NFA for an individual symbol is provided. You need to add the ability to construct more complex NFAs from these single symbol NFAs. Three of the commands of the interpreter require the ability to create new NFA from existing NFA, using one of the following actions: concatenate, union, and closure. You need to implement the same functionality for NFAs represented by the FiniteAutomaton class in the methods concat! union! closure!. You must construct the new NFA using the algorithm discussed in lecture. For exmple, given two NFA a and b as follows:

You should be able to use the algorithm described in class to create a single NFA representing:

NFA	Figure
ab
a\|b
a*

Note that though there are other algorithms for generating correct NFA for these operations, using them will yield a different NFA that will not pass the submit server tests. Your methods may (destructively) modify the current NFAs a and b. When you print out your NFA, you may notice differences between your output and the example output files provided in the public tests. The number assigned each state may be different, depending on the order you add new states to the FiniteAutomaton object. As a result, the order transitions are printed out may also differ. However, the submit server will ignore all output beginning with % (treating them as comments). So you can treat the FiniteAutomaton printout (which all begin with %) as diagnostic information that will not affect whether you pass a test.

Part 3: Reducing NFA to DFA

Once you have a NFA, invoking the toDFA method should create a new finite automaton representing a DFA created by the subset reduction method presented in class. I.e., the method should return a new FiniteAutomaton object that will accept only the strings accepted by the current FiniteAutomaton object, but which does not have epsilon-transitions or multiple transitions from a state with the same label.

Part 4: Minimizing DFA

Once you have a DFA, invoking the minimize! method should create a new finite automaton representing a minimal DFA created by the Moore reduction method presented in class. You may assume that the minimize! method will not be invoked on a NFA.

Submission

You can submit your project in two ways:

Submit your fa.rb file directly to the submit server by clicking on the submit link in the column "web submission".

Next, use the submit dialog to submit your fa.rb file directly.

Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file. Some students have mentioned problems with using Internet Explorer, because submissions being extracted in directories (e.g., "C:\My Documents\330\fa.rb") where the submit server could not find them. The problems went away when switching to the Mozilla Firefox browser.
Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p2.tar, To submit, go to the directory containing your project, then either execute submit.rb or type the following command directly:

java -jar submit.jar
You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

Successful submission # received for project 2

Hints and Tips

Be sure you have read and understand the project grading policies in the course syllabus. Do this well in advance of the project due date.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.

CMSC 330, Spring 2008

Organization of Programming Languages