I attach file that i need help
Microsoft Word - Pro1.docx In this nfa.py write a minimal finite-automata library. This is an NFA class (with DFA as a special case where delta happens to be a function) with methods: __init__, matches, epsilonClosure, move, NFA_to_DFA, statecount, isDFA, mi nimizeDFA, and generateSVG. Several of these (generateSVG, statecount, matches, isDFA) may not need to be modified at all, and several others have been partially stubbed out for you. • __init__: The constructor accepts a Regex object (defined in regex.py) that may be produced from a string using the regex procedure; e.g., NFA(regex("a*b")) should yield an NFA object that models the regular expression (a*)b. The Regex object yielded by regex("a*b") in this case will be the same as the expression: SeqRegex(StarRegex(CharRegex("a")),CharRegex("b")). • matches: This method accepts a string and returns True or False to indicate if the NFA/DFA receiving the call accepts the string. This code is already written and will work properly both for NFAs and DFAs if you add correct epsilonClosure and move methods. • epsilonClosure: This method takes a set of states in the receiving NFA and yields the set of states which are epsilon-reachable (i.e., reachable without consuming/reading any characters) from any in the input set. Note that the return value should be a superset of the input set as all states are epsilon-reachable from themselves. See the slides online for a formal definition. • move: This method takes a set of states and an (the next) input character, and returns the set of states reachable by traversing exactly one edge in this.delta annotated with the input character. See the slides for this definition as well. • NFA_to_DFA: This method constructs a new NFA object that encodes the NFA this as a DFA. This means the output value should pass the isDFA predicate’s test. This method should not modify this, but should produce a fresh DFA object using the subset construction we saw in class. • statecount: This method returns the number of states in the NFA/DFA. It is already written and will work properly if you use this.Q to maintain the set (or frozenset) of NFA states. • isDFA: This method checks if the receiver is a DFA specifically and not only an NFA. That is, it returns True if and only if this.delta is set of triples encoding a function (from a pair of a state and string to a state) and not a relation (False otherwise). You should not need to change this code unless you decide to represent this.delta in a different way. • minimizeDFA: (Extra credit.) This method should construct and yield a fresh DFA that encodes the current DFA in its minimal form. This method does not need to handle inputs that do not pass isDFA. Writing this method successfully is not required for full points on project 1. • generateSVG: This method is already written. You do not need to modify this method unless you represent NFAs/DFAs differently than the stubbed code suggests. It does not need to work properly; you may break this code and still earn 100% on the project, however, you may find it very helpful for debugging your code and visualizing the NFAs/DFAs your code produces as SVGs. Running this method will save a diagram, nfa.svg, in your working directory. Although not required, it is highly recommended that you write your NFA class in such a way as to keep this code functional. You will need to install graphviz on your system and also the graphviz python3 library if you wish to use this feature. Below are some other general guidelines: • You should not need to modify stubbed out code which is already in the starter. In some cases it will be safe, but its best to treat existing code as a guide to completing the NFA class correctly. When you first download the starter. Try opening a python3 REPL in the /p1/ folder and running: from nfa import * followed by NFA(regex("")).generateSVG() to see that this works. If it does not, you may need to ensure pip3 is installed and then run pip3 install graphviz to install the graphviz package. If it works properly you should see the following SVG when opening nfa.svg or nfa.html which will display the SVG and auto-refresh in case it is modified. • The class’s constructor __init__ consumes a regular expression object (these are defined in regex.py, which you do not need to modify at all, but is worth your perusal before starting.) This implements the RE->NFA constructions by recursively building NFAs. The starter has an example or two to get you started. You should try first implementing this correctly and seeing that your solutions work by testing them with matches and generateSVG. • You should implement move and epsilonClosure methods like we saw in class. epsilonClosure accepts a set of states and returns the set of states which are reachable while reading/consuming no characters. move accepts a set of states, and a single-character string, and returns the set of states reachable by consuming exactly that character via a single edge (no epsilon edges– triples (q0, "", q1) in self.delta. • NFA_to_DFA generates a newly allocated NFA instance which qualifies as a DFA in that isDFA will return true, and which is identical, in the language it denotes, to self, but is a (possibly non-minimal) DFA constructed via the subset algorithm. Note that the State class, defined in state.py can be instantiated with no arguments (in which case it is a fresh, anonymous, and always-unique state) or it can be instantiated with a key object or name object which determines its uniqueness (i.e. "q1"). Consider using the convention State(frozenset({...})) to name DFA states based on sets of NFA states when performing the subset construction. • Write your own tests! Write lots of your own tests.