This module defines an FSA class, for representing and operating onfinite-state automata (FSAs). FSAs can be used to represent regularexpressions and to test sequences for membership in the languagesdescribed by regular expressions.FSAs can be deterministic or nondeterministic, and they can containepsilon transitions. Methods to determinize an automaton (alsoeliminating its epsilon transitions), and to minimize an automaton,are provided.The transition labels for an FSA can be symbols from an alphabet, asin the standard formal definition of an FSA, but they can also beinstances which represent predicates. If these instances implementinstance.matches(), then the FSA nextState() function and accepts()predicate can be used. If they implement instance.complement() andinstance.intersection(), the FSA can be be determinized and minimized,to find a minimal deterministic FSA that accepts an equivalentlanguage.Quick Start----------Instances of FSA can be created out of labels (for instance, strings)by the singleton() function, and combined to create more complex FSAsthrough the complement(), closure(), concatenation(), union(), andother constructors. For example, concatenation(singleton('a'),union(singleton('b'), closure(singleton('c')))) creates an FSA thataccepts the strings 'a', 'ab', 'ac', 'acc', 'accc', and so on.Instances of FSA can also be created with the compileRE() function,which compiles a simple regular expression (using only '*', '?', '+','|', '(', and ')' as metacharacters) into an FSA. For example,compileRE('a(b|c*)') returns an FSA equivalent to the example in theprevious paragraph.FSAs can be determinized, to create equivalent FSAs (FSAs acceptingthe same language) with unique successor states for each input, andminimized, to create an equivalent deterministic FSA with the smallestnumber of states. FSAs can also be complemented, intersected, unioned,and so forth as described under 'FSA Functions' below.FSA Methods-----------The class FSA defines the following methods.Acceptance``````````fsa.nextStates(state, input)  returns a list of statesfsa.nextState(state, input)  returns None or a single state if  |nextStates| <= 1, otherwise it raises an exceptionfsa.nextStateSet(states, input)  returns a list of statesfsa.accepts(sequence)  returns true or falseAccessors and predicates````````````````````````isEmpty()  returns true iff the language accepted by the FSA is the empty languagelabels()  returns a list of labels that are used in any transitionnextAvailableState()  returns an integer n such that no states in the FSA  are numeric values >= nReductions``````````sorted(initial=0)  returns an equivalent FSA whose states are numbered  upwards from 0determinized()  returns an equivalent deterministic FSAminimized()  returns an equivalent minimal FSAtrimmed()  returns an equivalent FSA that contains no unreachable or dead  statesPresentation````````````toDotString()  returns a string suitable as *.dot file for the 'dot'  program from AT&T GraphVizview()  views the FSA with a gs viewer, if gs and dot are installedFSA Functions------------Construction from FSAs``````````````````````complement(a)  returns an fsa that accepts exactly those sequences that its  argument does notclosure(a)  returns an fsa that accepts sequences composed of zero or more  concatenations of sequences accepted by the argumentconcatenation(a, b)  returns an fsa that accepts sequences composed of a  sequence accepted by a, followed by a sequence accepted by bcontainment(a, occurrences=1)  returns an fsa that accepts sequences that  contain at least occurrences occurrences of a subsequence recognized by the  argument.difference(a, b)  returns an fsa that accepts those sequences accepted by a  but not bintersection(a, b)  returns an fsa that accepts sequences accepted by both a  and biteration(a, min=1, max=None)  returns an fsa that accepts sequences  consisting of from min to max (or any number, if max is None) of sequences  accepted by its first argumentoption(a)  equivalent to union(a, EMPTY_STRING_FSA)reverse(a)  returns an fsa that accepts strings whose reversal is accepted by  the argumentunion(a, b)  returns an fsa that accepts sequences accepted by both a and bPredicates``````````equivalent(a, b)  returns true iff a and b accept the same languageReductions (these equivalent to the similarly-named methods)````````````````````````````````````````````````````````````determinize(fsa)  returns an equivalent deterministic FSAminimize(fsa)  returns an equivalent minimal FSAsort(fsa, initial=0)  returns an equivalent FSA whose states are numbered from  initialtrim(fsa)  returns an equivalent FSA that contains no dead or unreachable  statesConstruction from labels````````````````````````compileRE(string)  returns an FSA that accepts the language described by  string, where string is a list of symbols and '*', '+', '?', and '|' operators,    with '(' and ')' to control precedence.sequence(sequence)  returns an fsa that accepts sequences that are matched by  the elements of the argument. For example, sequence('abc') returns an fsa that  accepts 'abc' and ['a', 'b', 'c'].singleton(label)  returns an fsa that accepts singletons whose elements are  matched by label. For example, singleton('a') returns an fsa that accepts only  the string 'a'.FSA Constants------------EMPTY_STRING_FSA is an FSA that accepts the language consisting onlyof the empty string.NULL_FSA is an FSA that accepts the null language.UNIVERSAL_FSA is an FSA that accepts S*, where S is any object.FSA instance creation---------------------FSA is initialized with a list of states, an alphabet, a list oftransition, an initial state, and a list of final states. If fsa is anFSA, fsa.tuple() returns these values in that order, i.e. (states,alphabet, transitions, initialState, finalStates). They're alsoavailable as fields of fsa with those names.Each element of transition is a tuple of a start state, an end state,and a label: (startState, endSTate, label).If the list of states is None, it's computed from initialState,finalStates, and the states in transitions.If alphabet is None, an open alphabet is used: labels are assumed tobe objects that implements label.matches(input), label.complement(),and label.intersection() as follows:    - label.matches(input) returns true iff label matches input    - label.complement() returnseither a label or a list of labels which,        together with the receiver, partition the input alphabet    - label.intersection(other) returns either None (if label and other don't        both match any symbol), or a label that matches the set of symbols that        both label and other matchAs a special case, strings can be used as labels. If a strings 'a' and'b' are used as a label and there's no alphabet, '~a' and '~b' aretheir respective complements, and '~a&~b' is the intersection of '~a'and '~b'. (The intersections of 'a' and 'b', 'a' and '~b', and '~a'and 'b' are, respectively, None, 'a', and 'b'.)Goals-----Design Goals:- easy to use- easy to read (simple implementation, direct expression of algorithms)- extensibleNon-Goals:- efficiency