he      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Safe9:;<=34*(c) Jooo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=UList Function: l1 - l2. Unlike List.(\), this function removes duplicates as well. Apply a function repeatedly, until a fix point is reached, i.e. until the result of the function is the same as the argument. 7Compute the permutations of a given list. For instance,Opermutations [1,2,3] = [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]    *(c) Jooo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=2Type of Table-based Deterministic Finite Automata. IThe type of Deterministic Finite Automata parameterized with the type st of states and sy of symbols. %Execute the transition function of a  v on an initial state and list of input symbol. Return the final state when all input symbols have been consumed.LTest whether the given automaton accepts the given list of input symbols.bTest whether the given automaton accepts the given list of input symbols (expressed as a fold).5Helper function to show the transition function of a  .Write a   to a Haskell module in a file.GCompute the labels with the same (giving) origin and destination states6Compute the destination states giving the origin statenCompute the states that can be reached from a state according to a given transition function and vocabulary(Produce the transition table of a given   . Given a  ,, it returns a list of triples of the form / (Origin,Symbol,Destination) & defining all the transitions of the  .Reconstruct a  v from a transition table. Given an automaton expressed by a transition table (ie a list of triples of the form 2 (Origin,Symbol,Destination)  it constructs a  . The other elements of the input tuple are the vocabulary, a set of states, an initial state, and a set of final states.Dfa to a Table-based DfaUAdd rows to a table-based Dfa, given a Dfa transition function and its vocabulary. Renames a  . It renames a DFA in such a way that the renaming of two isomorphic DFA returns the same DFA. It is the basis for the equivalence test for minimized DFA. Beautify a  * by assigning (natural) numbers to states.Compute the dead states of a  nCompute the size of a deterministic finite automaton. The size of an automaton is the number of its states.&Checks whether a state is dead or not.One state is dead when it is not possible to reach a final state from it. (probably we should consider that it has to be reachable from the initial state, as well)-Checks whether a state is a sync state or not[A sync state is a state that has transitions to itself for all symbols of the vocabulary7Compute the number of incoming arrows for a given state7Compute the number of outgoing arrows for a given state Print a   as a Haskell function.) Transition function Initial state Input symbols Final state Automaton Input symbols Automaton Input symbols AutomatonHaskell module nameTransition function VocabularyOrigin DestinationLabelsTansition Function VocabularyOriginDestination StatesTransition function VocabularyOriginReached states AutomatonTransition tableTuple-based Automaton AutomatonOriginal Automaton)Beautified Automaton (states as integers)Initial number?? AutomatonTransition tableTransition function VocabularyTable-based Dfa%Table-based Dfa with additional rows. AutomatonInitial state IDRenamed automaton Automaton Dead statesTransition Function VocabularySet of Final StatesStateTransition Function VocabularySet of Final StatesStateTransition Function Vocabulary Set of States DestinationNumber of ArrowsTransition Function VocabularyOriginNumber of Arrows    (   )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=!JType of Non-Deterministic Finite Automata. Parameterized with the type st of states and sy of symbols.#LTest whether the given automaton accepts the given list of input symbols.$%Execute the transition function of a !v on an initial state and list of input symbol. Return the final state when all input symbols have been consumed.2Apply the transition function to a list of states.%!Compute the eplison closure of a !.&5Helper function to show the transition function of a !.'9Produce the transition table of a given finite automaton.(@Compute the labels with the same (giving) origin and destination)6Compute the destination states giving the origin state*tCompute the states that can be reached from a given state according to a given transition function and vocabulary+(Produce the transition table of a given !.Given a !+ it returns a list of triples of the form / (Origin,Symbol,Destination) & defining all the transitions of the !.,Reconstruct a !% from a transition table. Given a !G expressed by a transition table (ie a list of triples of the form 8 (Origin,Maybe Symbol,Destination)  it constructs a !|. The other elements of the input tuple are the vocabulary, a set of states, and the sets of initial and final states- Renames a !..Compute the dead states of a !/5The size of an automaton is the number of its states.0Checks whether a ! state is dead or not.Checks whether a ! state is a sync state or not17Compute the number of incoming arrows for a given state27Compute the number of outgoing arrows for a given state3Print a ! as a Haskell function.!"# Automaton Input symbols$Transition functionInitial states Input symbolsReached statesTransition functionCurrent statesSymbol to consumeReached states%Transition functionCurrent statesReached states&' AutomatonHaskell module or file name()Transition Function VocabularyOriginDestination States*Transition Function VocabularyOriginReached States+ AutomatonTransition table, Tuple-based ! Automaton- AutomatonInitial integer numberRenamed Automaton. Automaton Dead States/ AutomatonSize0Transition Function VocabularySet of Final StatesState1Transition Function Vocabulary Set of States DestinationNumber of Arrows2Transition Function VocabularyOriginNumber of Arrows3!"#$%&'()*+,-./012!"#$%,()+*'-&/.012!"#$%&'()*+,-./0123None9:;<=4456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg4456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg4<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`a;456789:bcdefg-456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefgSafe9:;<=ijklmnopqrstuvwijklmnopqrstuvwlnkimjopqrsutvwijklmnopqrstuvw)(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=x)Minimize the number of states of a given  .. This function uses Brzozowski's algorithmy)Minimize the number of states of a given !.. This function uses Brzozowski's algorithmz)Minimize the number of states of a given  .This minimization algorithm is described in "An Introduction to Formal Languages and Automata", Peter Linz, 3rd Ed. Jones and Bartlett Publishers{)Minimize the number of states of a given  .(a third algorithm)| Reverse a  } Reverse a !~ Reverse a   into a   . It uses a !# as an intermediate representation.x Original  Equivalent Minimized  y Original !Equivalent Minimized  z Original  Equivalent Minimized  { Original  Equivalent Minimized    | Original   Resulting !} Original ! Resulting !~Orginal   Resulting  xyz{|}~xz{y|~}xyz{  |}~)(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Type of regular expressions.Empty Language Empty StringLiterals DisjuncionSequenceRepetition, possibly zero time#One or more times (extended RegExp)Optional (extended RegExp)Catamorphism induced by the  inductive data typeTest whether a match can be found for the given regular expression in the given sequence of characters. The regular expression is assumed not to contain  or  . See also matches'.Test whether a match can be found for the given regular expression in the given sequence of characters. The regular expression is allowed to contain  or . cProduce a list of all possible ways of splitting the input list into two parts. For instance, J splits "foo" = [("","foo"),("f","oo"),("fo","o"),("foo","")]  Produce a list of all possible ways of splitting the input list into two parts where the first part is non-empy. For instance, > splits "foo" = [("f","oo"),("fo","o"),("foo","")] Compute the size of a regular expression. We define the size of a regular expression as the number of occurrences of symbols of the alfabethgPrint regular expression to String as a catamorphism. A straightforward (catamorphic) show function.^(it produces too many brackets, making it difficult to read or understand the expression)MSimplify regular expressions according to the algebra of regular expressions.YRewrite extended regular expressions to plain regular expression. This means that the  and " constructors are normalized away.$Pretty print of regular expressions.(canonical) Regular Expression Input SymbolsRegular Expression  Input Symbols  Input List Splited List Regular ExpressionSizeRegular ExpressionString-based Regular Expression     )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<= Compute a ! from a . Compute a ! from a ]. Auxiliar function threading the context: the first available int to name the states Compute a   from a . (via the intermediate !)Regular expression AutomatonRegular expression Automaton )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Print a ! in GraphVizPrint a ! in GraphViz in a filePrint a   in GraphVizPrint a   in GraphViz in a filePrint a ! in GraphViz Automaton Graph's name Node's shape Orientation$Show function to print the state ids  None9:;<= Safe9:;<= )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=bCompute a regular expression that defines the transitions from an origin to a destination in a  .bCompute a regular expression that defines the transitions from an origin to a destination in a !.$Compute a regular expression from a  . Transition Function Vocabulary Origin StateDestination StateRegular ExpressionTransition Function Vocabulary Origin StateDestination StateRegular ExpressionDeterministic AutomatonEquivalent Regular Expression )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Parser for regular expressions Input symbolsRegular expression)(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Test whether two   are quivalent or not.Test whether two ! are quivalent or not.Test whether two  are quivalent or not.Test whether a list of  are quivalent or not.Deterministic AutomatonDeterministic Automaton Equivalent?Non-Deterministic AutomatonNon-Deterministic Automaton Equivalent?Regular ExpressionRegular Expression Equivalent?List of Regular Expressions Equivalent?)(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Class of Finite automatonInstance of class  for a !Instance of class  for a   )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Print a  in GraphViz-dot (as a string)Regular Expression (Abstract) Graph's Name.True: Deterministic ; False: Non-Deterministic Minimized?!Beautified? (states as numbers) Dead States? dot sentence Regular Expression Module Name Dot Graph!"#$%& !"#$%&Safe9:;<=' !"#$%&'()*+,-./01233456789:;<=>?@ABCDEFGHIJKLM NO!PQRSTUVWX.YZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ [ \ ] ^ _ WMtY              !"#$"HaLeX-1.2.2-BFaBnCH8vECKBU5wpDI1UhLanguage.HaLex.ParserLanguage.HaLex.UtilLanguage.HaLex.DfaLanguage.HaLex.NdfaLanguage.HaLex.DfaMonadLanguage.HaLex.FaOperationsLanguage.HaLex.MinimizeLanguage.HaLex.RegExpLanguage.HaLex.RegExp2FaLanguage.HaLex.FaAsDiGraphLanguage.HaLex.Examples.RobotLanguage.HaLex.Dfa2MDfaLanguage.HaLex.Fa2RegExpLanguage.HaLex.RegExpParserLanguage.HaLex.EquivalenceLanguage.HaLex.FaClassesLanguage.HaLex.RegExpAsDiGraphLanguage.HaLex.Examples.RealParsersymbolsatisfytokensucceed<|><*><$><->limit permutationsDfadfawalk dfaaccept showDfaDeltadfaIOtransitionsFromTodestinationsFromreachedStatesFromtransitionTableDfa ttDfa2DfabeautifyDfaWithSyncStdfa2tdfa renameDfa beautifyDfa dfadeadstatessizeDfaisStDeadisStSyncnumberIncomingArrowsnumberOutgoingArrows $fShowDfaNdfa ndfaacceptndfawalkepsilon_closure showNdfaDelta toHaskellndfaTransitionsFromTondfadestinationsFromndfareachedStatesFromtransitionTableNdfa ttNdfa2Ndfa renameNdfandfadeadstatessizeNdfa ndfaIsStDeadndfanumberIncomingArrowsndfanumberOutgoingArrows $fShowNdfaCodeOpenLocateInsertDeleteSaveEndInstr dfaaccept'runDfashowDfa showInDotshowElemsListPerLineshowInitialStateshowFinalStates' showArrows buildLinexpto deadstates deadstates' isSyncStaterobotmovesmoves2moves3moves4accvarGlobex2ex3 runAcceptex4 runAccept_ex4ex5 runAccept_ex5ex_int runAccept_intex6 runAccept_ex6te runAccept_teprconverteexpo runAccept_pr $fShowCodeCTstsDfandfa2ctndfa2dfalookupCTdfa2ndfa concatNdfa unionNdfastarNdfaplusNdfaexpNdfa concatDfaunionDfastarDfaplusDfa minimizeDfa minimizeNdfastdMinimizeDfa minimizeExp reverseDfa reverseNdfareverseDfaAsDfaRegExpEmptyEpsilonLiteralOrThenStar OneOrMoreOptional cataRegExp matchesREmatches' sizeRegExpshowREsimplifyRegExp extREtoRE $fShowRegExp $fReadRegExp $fEqRegExp regExp2Ndfa regExp2Ndfa' regExp2Dfa ndfa2graphvizndfa2graphviz2file dfa2graphvizdfa2graphviz2file tographviz genOneArrow tographvizIOdfa2DiGraphWithNoSyncStdfaDiGraphWithNoSyncStIOexgrobotMrobotM2acc2exShowshowAsAccumDfa showDfaMDeltadfa2MIOre2MHaskellModre2MDfafdfa_int regExpFromTondfaregExpFromTo dfa2RegExp parseRegExpequivDfa equivNdfaequivREequivREsFaacceptsizeFaequivminimize reverseFa toHaskell'toGraph toGraphIOunionFaconcatFastarFaplusFa $fFaNdfastsy $fFaDfastsy re2graphvizsinal''dre_intintdfad're_realre_real'cre_realrealdfa' realdfa'' realdfa''' realdfa''''genGraphrealdfa delta_realdfaisrealrealndfa deltaNdfa isrealNdfa insAllPosLst insAllPosinsAtPosTableDfa dfa2tdfaStepstPathlookupSt lookupNewSt getNewFinalSt giveNumberstsRHS allstsTableconsRowsoneRow newStsOfTablenewStsOfTableAux procrhsSts lookupNewStsgetNewStgetOldStdelta'old2new lookupFst lookupSndStDfaallstsCT ndfa2dfaStepfinalStatesDfaexpNdfa'undistinguishableeraseintersectdistinguishableremoveinaccessibleremoveinaccessible'rfindminauxpartes mesmoGrupo comparaDeltacomparaDeltaSimbsplits frontSplitsisSymbol showListMaybe groupMoves groupMoves'showNdfaArrows dfa2DiGraphIOdfa2DiGraphIO''toRegExp toRegExp2 toRegExp' toRegExp2'regularapplyDexprtermThentermfactor letterOrDigitspaces re2DiGraph re2DiGraph' re2DiGraph'' re2DiGraph'''re2DiGraphNdfa re2DiGraphIOabsRe2DiGraph_File