Friday, Sept 24th by 11:59 PM Monday, Sept 27th by 11:59 PM
Download CS340_Assign2.zip and import it into your Eclipse workspace (File->Import->General->Existing projects into workspace->Archive file.)
You should see a project called CS340_Assign2 in the Package Explorer.
Your task is to implement an algorithm to convert a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA).
Specifically, you will need to complete the implementation of the ConvertNFAToDFA class, and specifically, the convertToDFA() method of that class.
The Main class has a main method that can be used to run the overall program.
The overall program allows the user to enter a regular expression, and then enter strings. The program will print ACCEPT for each string that matches the regular expression, and REJECT for each string that does not match the regular expression.
The way the program works is that the regular expression is first converted to an NFA. The program then prompts the user to ask whether this NFA should be converted into a DFA. If the user answers no, then the NFA is executed against input strings using a slow simulation-based matching algorithm. If the user answers yes, then the ConvertNFAToDFA class is used to convert the NFA to a DFA, and a fast table-driven matching algorithm is used.
Example session (user input in bold):
Enter a regexp: a(bb|ccc|dddd)* Initial automaton is nondeterministic Convert the automaton to a DFA (yes/no)? no Enter strings: a ACCEPT aa REJECT abb ACCEPT abbb REJECT abbcccdddd ACCEPT acccb REJECT acccbb ACCEPT
The above session shows the matching being done by the slow NFA matching algorithm.
Another example session (user input in bold):
Enter a regexp: a(bb|ccc|dddd)* Initial automaton is nondeterministic Convert the automaton to a DFA (yes/no)? yes Converted automaton is deterministic Enter strings: a ACCEPT aa REJECT abb ACCEPT abbb REJECT abbcccdddd ACCEPT acccbb ACCEPT
This second session shows the NFA being converted to a DFA, and matching begin done with the fast DFA-based matching algorithm. The language recognized by the DFA is exactly the same as the one recognized by the original NFA.
Use the algorithm from Lecture 5.
The basic idea is that you will create a DFA where each state in the DFA corresponds to a set of states in the NFA.
In the program, the following classes are already implemented for you:
Class Purpose FiniteAutomaton Represents a finite automaton (NFA or DFA) State Represents a single state of a finite automaton StateSet Represents a set of states, useful for simulating an NFA Transition Represents a transition from one state to another FiniteAutomatonUtil Has some useful helper methods
Detailed API documentation is available.
Your grade will be determined as follows:
One extra credit option is available, for up to 20 extra points:
Instances of State, Transition, and StateSet can all be used as keys in TreeSet/TreeMap and HashSet/HashMap.
For example, you could use a TreeMap to keep track of the correspondence between sets of NFA states and DFA states as follows:
TreeMap<StateSet, State> nfaStateSetToDfaStateMap = new TreeMap<StateSet, State>();
Essentially, this can serve as the "table" data structure described in the algorithm in the lecture notes.
Export your completed Eclipse project to a zip file by right-clicking on the name of the project (CS340_Assign2) and choosing Export->General->Archive File.
Upload the zip file to the submission server as assign2. The URL of the server is
IMPORTANT: after uploading, you should download a copy of your submission and double-check it to make sure that it contains the correct files. You are responsible for making sure your submission is correct. You may receive a grade of 0 for an incorrectly submitted assignment.