úΛT”ĖM      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKL!Error monad for reading FSMs in. +Errors when reading matrices from strings. Explanatory message Offending value !Words are lists of symbols. <Finite state machine whose nodes are labelled with type sy. MActions are lists of DestinationSets, indexed by source  . #Destination sets are just lists of s. )States are integers, counting from zero. 3Create an FSM from a list of symbol, Action pairs. 1Turn an FSM into a list of symbol, Action pairs. ,Delete a symbol and its action from an FSM. Look up a symbol's   in an  Map a function over the FSM. "Compute the list of states of the . Only really meaningful  if the FSM's well-formedness is not  BadLengths. With current  implementation, is just [0..n] for some n (or empty). Compute the alphabet of an . ;Build an action given a nested list of destination states. ABuild a deterministic action given a list of destination states.  Append two  s, ie compute the   corresponding to 6 the application of the first followed by the second. N Compute the   reached by following some    from some .  Compute the   for some  over some  . The word & might contain symbols outside the FSM's alphabet, so the result  could be Nothing.  Test if two 's are action-equivalent over some FSM.  Compute the   for some  at some  of  an 1. The word might contain symbols outside the FSM's C alphabet, or the state might be out of range, so the result could  be Nothing.  Test if two %s are destination-equivalent at some  of  an . -Compute the identity action for a given FSM. 9Compute the identity action for a given number of states  Test if an   is deterministic or not. !Compute whether an  is deterministic or not. " Normalise an , i.e. normalise all its Actions. #  !"#  "# !   !"#%An 8 is well-formed if all its actions are the same length, B none of its actions contain destinations which are out of range,  and it is not disjoint. & Well-formed. '9The FSM is disconnected, i.e. not even weakly-connected. > Carries a list of its weakly-connected components (each is a  list of s). (Some  .s contain out-of-range (negative or too-high) > destinations. Carries a sorted list of all such actions and  their corresponding symbols. )Lengths of Actions in the  don't all match. Carries a  sorted list of (symbol,   length) pairs, one for every  symbol in the alphabet of the . * Check if an  is well-formed or not. +'Given an FSM, normalise it and check it's well-formed. -This should be called whenever an FSM is read/computed from an = outside source. If parsing, the right time to call this is  immediately after you''ve decided if the parse of the FSM was D successful or not. (In other words, here are some static checks!) O%&'()*+%)('&*+%)('&&'()*+PQ This module'5s internal represenation of adjacency matrices is as E nested lists of booleans. These are only ever used as intermediate = data structures, and should not be generated or manipulated ; directly. If you want to work with actions, use the Core   , type. If you want serialised matrices for E storage or transmission, convert them to strings of 0s and 1s using  the functions in this module. ,Load an $ from action matrices, given a path  to an ActionSpec file. -Save an # to an ActionSpec file (whose path @ is specified) and a set of action matrices (whose paths may be ? optionally specified using a (label, path) association list). R>Parse an fsmActionSpec string to a (label, ActionMatrix path)  association list. S"Parser for fsmActionSpec strings. .4Given a (symbol, path) association list, compute an  - whose actions are read from action matrices A in the specified paths, and associated with their corresponding  symbols. T/BGiven a (symbol, ActionMatrix string) association list, parse the ; strings and construct an FSM. Includes normalisation and D well-formedness checks. Parse errors in individual action strings @ result in an error here (ReadFsmMonad is in the Either monad). >Note that if the same symbol appears multiple times, only one  instance will appear in the ; the choice of which  appears is not defined. 03Parse an action matrix string, and turn it into an   . U&Parse an action matrix from a string. ?The string being parsed should contain newline-separated rows, E where each row contains comma-separated cells, where each cell is a + 0 or a 1. Trailing newlines are ignored. V Given an Q, compute the corresponding   . W Given an P', compute the list of indices of cells > in the row which are set (i.e. which represent transitions). 1;Pretty-print a string FSM into an ActionSpec string and an B (ActionMatrix path, ActionMatrix string) association list. (The 5 paths will be interpreted relative to the ActionSpec' s location.) > Filenames (per action label) may be specified by providing a @ (label, path) association list; whenever a lookup in that list . fails, a default is computed from the label. X;Compute the default path for a symbol; we take the symbol, E replace various undesirable characters with underscores, and append   .actionmx. Y20Pretty-print an action in action matrix format. Z,-./012,-./012,-./012$Compute an FSM's weakly-connected components. [AA NodeMap is a map from graph node numbers to FSM state numbers, 6 the inverse of the indexing produced by labNodes, ie $ forall n . (fst (labNodes g !! n)) \ nodeMap g == n ]<A DestsMap maps (action symbol, source graph node) pairs to  [destination graph node]* lists, which provide a handy lookup when  building  s. 3 Subclass ^ so that _ calls on `s and as  don't get quotes inserted. 45When converting an  into a graph, do we keep D all self-loops, or only those which are sources of nondeterminism? 6Trim any which aren't nondeterminism sources. 7Keep them all 83Turn an FSM into an fgl graph with labelled edges. bcdefg9Compute an FSM'!s strongly-connected components. h@The PatriciaTree instance of Graph is faster, but not generally  useful to us because it doesn'#t allow multiple edges between the 9 same pair of nodes. For SCC checks, however, that doesn' t matter,  so we use it. :Turn an FSM into a ij, trimming any  self-loops which aren't sources of nondeterminism. ;<&Turn an FSM into a GML-formatted graph', trimming any self-loops  which aren't sources of nondeterminism. kl=BTurn an FGL graph (interpreted as being a directed graph) into an D FSM. Self-loops are inserted as required. Also returns a list of  the graph'8s labelled nodes, since the labels are discarded by the 0 FSM construction. FSM states are numbered [0..] and thus may be @ used as an index into that list of labelled nodes, in order to > relate FSM states back to the original graph nodes and their  labels. m;Turn a graph into a list of its labelled nodes (indexed by 1 corresponding FSM state) and a list of (symbol,    ) pairs. nopq@Given a labelled directed graph, compute the list of its unique , labels, which will be the corresponding FSM' s symbols. rBuild a DestsMap from a graph. sConstruct a NodeMap. tAPerform a node -> state lookup in a NodeMap; throws an exception  if it fails, which it shouldn' t ever here. $3456789:;<= 5768;9$34:<= $3445766789:;<= uv>Load an  from an FsmEdges file. ?Save an  to an FsmMatrix file. @<Parse an FsmEdges-formatted FSM held in a string. Includes + normalisation and well-formedness checks. wxA/Pretty-print a string FSM in FsmMatrix format. y>?@A>?@A>?@ABLoad an  from an FsmMatrix file. CSave an  to an FsmMatrix file. D=Parse an FsmMatrix-formatted FSM held in a string. Includes + normalisation and well-formedness checks. z{E/Pretty-print a string FSM in FsmMatrix format. |BCDEBCDEBCDE F Known FSM I/ O formats. GFsmMatrix format: use  B and  C ; filename 0 extensions: mx, matrix, fsmmx, fsmmatrix, fsm. HFsmEdges format: use  > and  ? ; filename 2 extensions: edges, fsmedges, graph, mathematica. IActionMatrix format: use  , and  - ; filename - extensions: actions, actionspec, actionmxs,  actionmatrices, fsmactions. } Mapping from F' formats to lists of expected filename  extensions for those formats. J#Given a path, return a list of all F formats, with guesses 1 (according to the file extension) at the front. ~4Reverse lookup in map from keys to lists of values. KRead an % from a file. If the user specifies  any F4 formats, try each of those in turn; otherwise, try D every format known, using the filename extension to guess which to  try first. +The returned value is either the resultant , E or the error message produced by trying to load it with the _first_ C format (so in the case of guessing formats, if the guess is wrong E and the file is corrupt, you might get an unhelpful error message). 9Try loading an FSM from a file with a particular format. LSave an # to a file. If the user specifies  an F7 format, it is used; otherwise, it is guessed from the ; filename extension (and failing that, the first guess, ie  I , is used). FGHIJKLFIHGJKLFIHGGHIJKL€        !"#$%&'()**+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdbcebfghijklmnopqrstrstuvwxyz{|}~~€‚ƒ„…†‡ˆfsmActions-0.4.2Data.FsmActions.ErrorData.FsmActionsData.FsmActions.GraphData.FsmActions.WellFormedData.FsmActions.ActionMatrixData.FsmActions.FsmEdgesData.FsmActions.FsmMatrixData.FsmActions.IO ReadFsmMonadFsmErrormsgvalueWordFSMActiondestinationSetsDestinationSet destinationsStatefromListtoListdeletelookupfsmMapstatesalphabetmkAction mkDActionappend actionLookupaction actionEquivdestinationSetdestinationEquiv fsmIdentityidentity isDActionisDFSM normalisenormaliseActionweakCCs WellFormed Disconnected BadActions BadLengths isWellFormed polishFSMloadActionMxFsmsaveActionMxFsmparseFsmActionMxFilesparseFsmActionMxs parseActionMxprintFsmActionMx printActionMx CleanShow cleanShow SelfLoopsTrimKeepfsmToFGL strongCCsfsmToDotfglDotfsmToGMLfglToFsm loadFsmEdges saveFsmEdges parseFsmEdges printFsmEdges loadFsmMx saveFsmMx parseFsmMx printFsmMxFsmIO FsmMatrixFsmEdgesFsmActionMatrices fsmFormatsloadFsmsaveFsm appendAtStateallSameActionMatrixRow ActionMatrixparseFsmActionSpecfsmActionSpecParserliftMSndactionMxParserinterpretActionMxparseActionMxRow defaultPath ppActionSpec ppActionMxNodeMapcontainers-0.4.0.0Data.MapDestsMapbaseGHC.ShowShowshowGHC.BaseStringghc-prim GHC.TypesChar fsmToFGL'fsmEdges symbolEdges syStateEdges syStateEdges' zipWithIndexfsmToPatriciaTreegraphviz-2999.9.0.0Data.GraphViz.TypesDotGraphgmlNodegmlEdge graphActions mkActions mkDestSetsymbols mkDestsMap mkNodeMap nodeToStateEdgefsmEdgesParser edgesToFGL ppFsmEdgesfsmMatrixParserinterpretFsmMxppFsmMx fsmIOExtsrLookup tryLoadFsm