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:
computer science
Description
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.
