-      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ *(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) Joo Saraiva 2001,2002,2003,2004,2005, 2016LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Type of regular expressions.Empty Language Empty StringLiterals DisjuncionSequence Repetition, possibly zero time #One or more times (extended RegExp) Optional (extended RegExp) Set (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 ListRegular ExpressionSizeRegular ExpressionString-based Regular Expression     Safe9:;<=    34/(c) Joo Saraiva 2001,2002,2003,2004,2005, 2016LGPLjas@di.uminho.pt provisionalportableSafe9:;<= Parser for regular expressions  Input symbolsRegular expressionfirst elem of the setlast elem of the setRegular Expression for the set  *(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 states(6Compute the destination states giving the origin state)nCompute 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 !.+(Produce the transition table of a given !. Given a !,, it returns a list of triples of the form * (Origin,[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.0 Beautify a !* by assigning (natural) numbers to states.1Compute the dead states of a !2nCompute the size of a deterministic finite automaton. The size of an automaton is the number of its states.3&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)4-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 vocabulary57Compute the number of incoming arrows for a given state67Compute the number of outgoing arrows for a given state7Print a ! as a Haskell function.*!"#Transition function Initial state Input symbols Final state Automaton Input symbols$ Automaton Input symbols%& AutomatonHaskell module name'Transition function VocabularyOrigin DestinationLabels(Tansition Function VocabularyOriginDestination States)Transition function VocabularyOriginReached states* AutomatonTransition table+ AutomatonTransition table,Tuple-based Automaton Automaton-Original Automaton)Beautified Automaton (states as integers)Initial number??. AutomatonTransition tableTransition function VocabularyTable-based Dfa%Table-based Dfa with additional rows.  / AutomatonInitial state IDRenamed automaton   01 Automaton Dead states23Transition Function VocabularySet of Final StatesState4Transition Function VocabularySet of Final StatesState5Transition Function Vocabulary Set of States DestinationNumber of Arrows6Transition Function VocabularyOriginNumber of Arrows7!"#$%&'()*+,-./0123456!"$#,.'(*+)0/%-&213465)!"#$%&'()*+,-.  /   01234567/(c) Joo Saraiva 2001,2002,2003,2004,2005, 2016LGPLsaraiva@di.uminho.pt provisionalportableSafe9:;<=8JType 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 8v 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 8.=5Helper function to show the transition function of a 8.>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 stateAtCompute the states that can be reached from a given state according to a given transition function and vocabularyB(Produce the transition table of a given 8.Given a 8+ it returns a list of triples of the form / (Origin,Symbol,Destination) & defining all the transitions of the 8.CReconstruct a 8% from a transition table. Given a 8G expressed by a transition table (ie a list of triples of the form 8 (Origin,Maybe Symbol,Destination)  it constructs a 8|. The other elements of the input tuple are the vocabulary, a set of states, and the sets of initial and final statesD Renames a 8.ECompute the dead states of a 8F5The size of an automaton is the number of its states.GChecks whether a 8 state is dead or not.HChecks whether a 8 state is a sync state or notI7Compute the number of incoming arrows for a given stateJ7Compute the number of outgoing arrows for a given stateKPrint a 8 as a Haskell function.89: 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 StatesATransition Function VocabularyOriginReached StatesB AutomatonTransition tableC Tuple-based 8 AutomatonD AutomatonInitial integer numberRenamed AutomatonE Automaton Dead StatesF AutomatonSizeGTransition Function VocabularySet of Final StatesStateHTransition Function VocabularySet of Final StatesStateITransition Function Vocabulary Set of States DestinationNumber of ArrowsJTransition Function VocabularyOriginNumber of ArrowsK89:;<=>?@ABCDEFGHIJ89:;<C?@BA>D=FEGHIJ89:;<=>?@ABCDEFGHIJKNone9:;<=4LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~4LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~4TUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxySLMNOPQRz{|}~-LMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~)(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 8.$Compute a regular expression from a !. Transition Function Vocabulary Origin StateDestination StateRegular ExpressionTransition Function Vocabulary Origin StateDestination StateRegular ExpressionDeterministic AutomatonEquivalent Regular Expression  Safe9:;<= !"# !"# )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=)Minimize the number of states of a given !.. This function uses Brzozowski's algorithm)Minimize the number of states of a given 8.. This function uses Brzozowski's algorithm)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 8 Reverse a ! into a ! . It uses a 8# as an intermediate representation. Original !Equivalent Minimized ! Original 8Equivalent Minimized ! Original !Equivalent Minimized !$%&'( Original !Equivalent Minimized !)*+,-. Original ! Resulting 8 Original 8 Resulting 8Orginal ! Resulting !$%&'()*+,-. .(c) Joo Saraiva 2001,2002,2003,2004,2005,2016LGPLjas@di.uminho.pt provisionalportableSafe9:;<= Compute a 8 from a . Compute a 8 from a ]. Auxiliar function threading the context: the first available int to name the states Compute a ! from a . (via the intermediate 8)Regular expression AutomatonRegular expression Automaton Safe9:;<= )(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Test whether two ! are quivalent or not.Test whether two 8 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,2005, 2016LGPLsaraiva@di.uminho.pt provisionalportableSafe9:;<= Print a 8 in GraphVizPrint a 8 in GraphViz in a filePrint a ! in GraphVizPrint a ! in GraphViz in a filePrint a 8, in GraphViz/dot notation (default function)Print a 8 in GraphViz/dot notation/6Show the arrows between nodes (states) induced by the 8 transitions.0Group labels with same origin and destination. Given the Transition Table of a Ndfa it groups the transtions with the same origin and destination into a single transition, whose transtion is the list of labels of the original transtions.Save a 8* in a GraphViz/dot file (default function)Save a 8 in a GraphViz/dot file Automaton Graph's name Node's shape Orientation$Show function to print the state ids Automaton Graph's name Node's shape Orientation$Show function to print the state ids!Show function to print the labelsShow dead states?Show sync states?/ Automaton$Show function to print the state ids!Show function to print the labelsShow dead states?Show sync states?012 Automaton Graph's name Node's shape Orientation$Show function to print the state ids Automaton Graph's name Node's shape Orientation$Show function to print the state ids!Show function to print the labelsShow dead states?Show sync states?34 /01234None9:;<= )(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 sentence5Regular Expression Module Name Dot Graph6789:;56789:;(c) Joo Saraiva 2017LGPLjas@di.uminho.pt provisionalportableSafe9:;<=UGenerates a set of sentences of the language defined by a given Regular ExpressioneGenerates a set of sentences of the language defined by a given NonDerterministic Finite AutomatonbGenerates a set of sentences of the language defined by a given Deterministic Finite Automaton.It computes a set of paths starting from the start state and ending in an accepting state, which include all transitions/edges of the automaton.vThis function does not computes the smallest set (of paths/sentebces), as computed by the "Chinese Postman Problem"Function written by MSc student Jos Nuno Macedo (72424) in the context of the 2016/17 edition of the course "Analysis and Testing of Software", MIEI, Univ. Minho.<This auxiliar function uses the transition table computed from the given automaton to generate a finite set of sentences the the language.=This function generates all paths (corresponding to valid sentences of the language) that cover all transitions of the finite automaton. The transition table serves two purposes when calling this function: - to know the transitions of the automaton - to serve has the state recording all transitions not used (yet) (in the begining this list should be the full transition table of the dfa, and the function terminates when this list is empty: no more tarnsitions need to be covered)>This function computes one path from a given start state to a given final state. The function does not repeat transitions. This function "walks backwards": it starts from the final state back to the start one.CIt receives the Dfa's transition table (tt), the table with the transitions that Can Be Used (cbu), the labels of the transitions used thus far (sys), the final state (ft), the start state (st). It returns a pair: the transitions that were not used in this path the list of labels used in the pathcThis function computes one sentence of the language defined by a deterministic fininte automaton<= AutomatonDfa's Transition Table!Table with transitions to be usedList of sentences>Dfa's Transition Table!Table with transitions to be usedlist of labels (used so far)  final state start state<=>)(c) Joo Saraiva 2001,2002,2003,2004,2005LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Class of Finite automatonInstance of class  for a 8Instance of class  for a !Safe9:;<=(c) Joo Saraiva 2017LGPLjas@di.uminho.pt provisionalportableSafe9:;<=Test the size of finite automata The size (ie number of states) of a minimized dfa is always less of equal than the size of an equivalent ndfa or dfa.KTest the acceptance of generated sentences The accpetance functions for , 8 and !J should accept all sentences of the language of an equivalent reg. exp.?@ABCDEFGHIJK?@ABCDEFGHIJK(c) Joo Saraiva 2017LGPLjas@di.uminho.pt provisionalportableSafe9:;<=L !"#$%&'()*+,-./01234567789:;<=>?@ABCDEFGHIJKLMMNOPQRSTUVWXYZ[\]^_`abcdefg778h9ij:klmnopqrsHtuvwxyz{|}~  vwxyzrh        ! "   # $ % & ' ( ) * + , - . /0123456789:;<=>?@ABCDEFGHIJK"HaLeX-1.2.6-9DvRolZpaK0FGtDAcLCXlKLanguage.HaLex.UtilLanguage.HaLex.RegExpLanguage.HaLex.ParserLanguage.HaLex.RegExpParserLanguage.HaLex.DfaLanguage.HaLex.NdfaLanguage.HaLex.DfaMonadLanguage.HaLex.Fa2RegExpLanguage.HaLex.FaOperationsLanguage.HaLex.MinimizeLanguage.HaLex.RegExp2FaLanguage.HaLex.Dfa2MDfaLanguage.HaLex.EquivalenceLanguage.HaLex.FaAsDiGraphLanguage.HaLex.Examples.RobotLanguage.HaLex.RegExpAsDiGraphLanguage.HaLex.SentencesLanguage.HaLex.FaClassesLanguage.HaLex.Examples.RealLanguage.HaLex.Test_HaLex$Language.HaLex.Test_HaLex_Quickcheck<->limit permutationsRegExpEmptyEpsilonLiteralOrThenStar OneOrMoreOptionalRESet cataRegExp matchesREmatches' sizeRegExpshowREsimplifyRegExp extREtoRE $fShowRegExp $fReadRegExp $fEqRegExpParsersymbolsatisfytokensucceed<|><*><$> oneOrMore parseRegExpDfadfawalk dfaaccept showDfaDeltadfaIOtransitionsFromTodestinationsFromreachedStatesFromtransitionTableDfatransitionTableDfa' ttDfa2DfabeautifyDfaWithSyncStdfa2tdfa renameDfa beautifyDfa dfadeadstatessizeDfaisStDeadisStSyncnumberIncomingArrowsnumberOutgoingArrows $fShowDfaNdfa ndfaacceptndfawalkepsilon_closure showNdfaDelta toHaskellndfaTransitionsFromTondfadestinationsFromndfareachedStatesFromtransitionTableNdfa ttNdfa2Ndfa renameNdfandfadeadstatessizeNdfa ndfaIsStDeadndfaIsSyncStatendfanumberIncomingArrowsndfanumberOutgoingArrows $fShowNdfaCodeOpenLocateInsertDeleteSaveEndInstr dfaaccept'runDfashowDfa showInDotshowElemsListPerLineshowInitialStateshowFinalStates' showArrows buildLinexpto deadstates deadstates' isSyncStaterobotmovesmoves2moves3moves4accvarGlobex2ex3 runAcceptex4 runAccept_ex4ex5 runAccept_ex5ex_int runAccept_intex6 runAccept_ex6te runAccept_teprconverteexpo runAccept_pr $fShowCode regExpFromTondfaregExpFromTo dfa2RegExpCTstsDfandfa2ctndfa2dfalookupCTdfa2ndfa concatNdfa unionNdfastarNdfaplusNdfaexpNdfa concatDfaunionDfastarDfaplusDfa minimizeDfa minimizeNdfastdMinimizeDfa minimizeExp reverseDfa reverseNdfareverseDfaAsDfa regExp2Ndfa regExp2Ndfa' regExp2DfashowAsAccumDfa showDfaMDeltadfa2MIOre2MHaskellModre2MDfafdfa_intequivDfa equivNdfaequivREequivREs ndfa2graphvizndfa2graphviz2file dfa2graphvizdfa2graphviz2file tographviz tographviz' genOneArrow tographvizIO tographvizIO'dfa2DiGraphWithNoSyncStdfaDiGraphWithNoSyncStIOexgrobotMrobotM2acc2exShow re2graphvizsentencesRegExp sentencesNdfa sentencesDfa onePathDfaFaacceptsizeFaequivminimize reverseFa sentences toHaskell'toGraph toGraphIOunionFaconcatFastarFaplusFa $fFaNdfastsy $fFaDfastsysinal''dre_intintdfad're_realre_real'cre_realrealdfa' realdfa'' realdfa''' realdfa''''genGraphrealdfa delta_realdfaisrealrealndfa deltaNdfa isrealNdfa test_size_fatest_gen_sentences genRegExp digRegExp digRegExp' genRegExp'exRegExp$fArbitraryRegExp insAllPosLst insAllPosinsAtPossplits frontSplitsisSymbolexprtermThentermfactorrange letterOrDigit setRegExpasciispacesTableDfa dfa2tdfaStepstPathlookupSt lookupNewSt getNewFinalSt giveNumberstsRHS allstsTableconsRowsoneRow newStsOfTablenewStsOfTableAux procrhsSts lookupNewStsgetNewStgetOldStdelta'old2new lookupFst lookupSndtoRegExp toRegExp2 toRegExp' toRegExp2'regularapplyDStDfaallstsCT ndfa2dfaStepfinalStatesDfaexpNdfa'undistinguishableeraseintersectdistinguishableremoveinaccessibleremoveinaccessible'rfindminauxpartes mesmoGrupo comparaDeltacomparaDeltaSimbshowNdfaArrows groupMoves groupMoves' showLabels dfa2DiGraphIOdfa2DiGraphIO'' re2DiGraph re2DiGraph' re2DiGraph'' re2DiGraph'''re2DiGraphNdfa re2DiGraphIOabsRe2DiGraph_File sentencesDfa'onePathrere''ndfadfadfa_mindfa_min'test_acceptNdfatest_acceptDfatest_acceptDfamin dfaToHaskellre'main