
CMSC 330, Fall 2010Organization of Programming LanguagesProject 2  Finite Automata Interpreter
IntroductionYou will need to implement code to build up NFAs, convert them to DFAs, minimize DFAs, and test whether a string is accepted by a DFA. You will do this by extending a provided FiniteAutomaton class that operates as part of a simple interpreter. Getting StartedDownload the following archive file p2.zip and extract its contents.Along with files used to make direct submissions to the submit server (submit.jar, .submit, submit.rb), you will find the following project files:
The fa.rb file you downloaded already implements a simple interpreter for commands to build/transform finite automata, print out various properties about them (such as the number of states they have, or the strings they accept), and use them to accept/reject particular strings. The interpreter operates using a stack, where each object on the stack is a finite automaton. Commands pop zero, one, or two finite automata from the stack and push zero or one finite automata on stack as a result, along with potentially printing output. Each command is separated by a whitespace: there is nothing special about line breaks. The interpreter (implemented in toplevel function interpreter) works by creating new FiniteAutomaton objects and invoking methods on them. The interpreter will accept the following commands:
ExampleHere is an example session with the interpreter:a b . PRINT SIZE c  * DONEThe first line creates an FA that accepts exactly the string a, and pushes it on the stack. The second line creates an FA that accepts exactly the string b, and pushes it on the stack. The third line pops these two automata off of the stack, and constructs a new automaton that accepts the concatenation of strings accepted by the two, i.e., ab. This new automaton is pushed back on the stack, and is now the only automaton on the stack. The next command prints out this automaton (leaving it on the stack), producing output like the following: % Start 0 % Final { 3 } % States { 0 1 2 3 } % Alphabet { a b } % Transitions { % (0 a 1) % (1 2) % (2 b 3) % }Note that different implementations might produce different output in this case, most notably because they could choose different names for states. The next command prints the number of states in the topmost automaton (leaving it onstack), in this case 4. The next command constructs an automaton that accepts the string c and pushes it onstack. The subsequent command pops off this automaton and combines with the the ab automaton also onstack to produce the automaton implementing abc, pushing it onstack. The next command creates a new automaton from this one, implementing (abc)*. The final command terminates the session. As mentioned, linebreaks are immaterial. Exactly the same results would be produced by the input a b . PRINT SIZE c  * DONE Part 1: Extend the FiniteAutomaton class to support NFAsThe FiniteAutomaton class in fa.rb is based on the DFA class used as an example during discussion section. The original DFA class is 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 this FiniteAutomaton class to represent both NFAs and DFAs. In particular, your modified class should support additional features allowed by NFAs, such as epsilontransitions and multiple transitions with the same label. You may choose to represent epsilontransitions as transitions labeled with the empty string "" (as we do in our reference implementation used to produce the sample public outputs) or some other label.If an automaton is deterministic (i.e., it represents a DFA), it should be able to run on input strings input strings; i.e., the accept? method should return true if your FiniteAutomaton object is actually a DFA and it accepts the string; the accept? method returns false otherwise (that is, if the automaton is actually an NFA, or if it does not accept the string). Part 2: Building NFAs out of other NFAsThe 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 singlesymbol 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. In particular, 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:
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. You can assume there is only one start state for each NFA. Part 3: Reducing NFA to DFAOnce 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 epsilontransitions or multiple transitions from a state with the same label.Part 4: Minimizing DFAOnce you have a DFA, invoking the minimize method should create and return a new finite automaton representing a minimal DFA accepting the same language. You can either create a new DFA or (destructively) modify the existing FiniteAutomaton object on which mimimize is called; in either case you need to return the minimized DFA. You may assume that the minimize method will not be invoked on a NFA, but only the DFAs created by the toDFA method. As a result you do not need to handle dead states (since if you implemented the previous parts of the project correctly, these DFAs will not have dead states).SubmissionYou can submit your project in two ways:
Hints and TipsAcademic IntegrityThe 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 syllabusplease review it at this time. 