úΙ«“~J      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHI Safe-Inferred!Error monad for reading FSMs in. +Errors when reading matrices from strings. Explanatory message Offending value JKLJKL Safe-InferredWords are lists of symbols. <Finite state machine whose nodes are labelled with type sy. Actions 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.  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. !M N !"#  !"#  "# !M  N !"# Safe-Inferred%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%&'()*+%)('&*+%)('&*+ONoneP 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). Q>Parse an fsmActionSpec string to a (label, ActionMatrix path)  association list. R"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. /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  . S&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. T Given an P, compute the corresponding  . U Given an V', 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. W;Compute the default path for a symbol; we take the symbol, E replace various undesirable characters with underscores, and append   .actionmx. 20Pretty-print an action in action matrix format. VP,-QR.X/0STU1WY2Z,-./012,-./012VP,-QR.X/0STU1WY2ZNone$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. 3When converting an  into a graph, do we keep D all self-loops, or only those which are sources of nondeterminism? 4Trim any which aren't nondeterminism sources. 5Keep them all 63Turn an FSM into an fgl graph with labelled edges. 7Compute an FSM'!s strongly-connected components. ^@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. 8Turn an FSM into a _, trimming any  self-loops which aren't sources of nondeterminism. :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. `;Turn a graph into a list of its labelled nodes (indexed by 1 corresponding FSM state) and a list of (symbol,   ) pairs. a@Given a labelled directed graph, compute the list of its unique , labels, which will be the corresponding FSM' s symbols. bBuild a DestsMap from a graph. cConstruct a NodeMap. dAPerform a node -> state lookup in a NodeMap; throws an exception  if it fails, which it shouldn' t ever here. $[]3456efghij7^89:`klmabcd $3456789: 354697$8:$[]3546efghij7^89:`klmabcdNone;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. >/Pretty-print a string FSM in FsmMatrix format. no;<=pq>r;<=>;<=>no;<=pq>r Safe-Inferred?Load an  from an FsmMatrix file. @Save an  to an FsmMatrix file. A=Parse an FsmMatrix-formatted FSM held in a string. Includes + normalisation and well-formedness checks. B/Pretty-print a string FSM in FsmMatrix format. ?@AstBu?@AB?@AB?@AstBuNone C Known FSM I/ O formats. DFsmMatrix format: use  ? and  @ ; filename 0 extensions: mx, matrix, fsmmx, fsmmatrix, fsm. EFsmEdges format: use  ; and  < ; filename 2 extensions: edges, fsmedges, graph, mathematica. FActionMatrix format: use  , and  - ; filename - extensions: actions, actionspec, actionmxs,  actionmatrices, fsmactions. v Mapping from C' formats to lists of expected filename  extensions for those formats. G#Given a path, return a list of all C formats, with guesses 1 (according to the file extension) at the front. w4Reverse lookup in map from keys to lists of values. HRead an % from a file. If the user specifies  any C4 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). x9Try loading an FSM from a file with a particular format. ISave an # to a file. If the user specifies  an C7 format, it is used; otherwise, it is guessed from the ; filename extension (and failing that, the first guess, ie  F , is used). CDEFvGwHxICDEFGHICFEDGHICFEDvGwHxIy        !"#$%&'()**+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrsstuvwxyz{|}fsmActions-0.4.4Data.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 SelfLoopsTrimKeepfsmToFGL strongCCsfsmToDotfglDotfglToFsm loadFsmEdges saveFsmEdges parseFsmEdges printFsmEdges loadFsmMx saveFsmMx parseFsmMx printFsmMxFsmIO FsmMatrixFsmEdgesFsmActionMatrices fsmFormatsloadFsmsaveFsm$fShowFsmError$fErrorFsmError$fExceptionFsmError appendAtStateallSame ActionMatrixparseFsmActionSpecfsmActionSpecParseractionMxParserinterpretActionMxparseActionMxRowActionMatrixRow defaultPathliftMSnd ppActionSpec ppActionMxNodeMapcontainers-0.5.0.0 Data.Map.BaseDestsMapfsmToPatriciaTreegraphviz-2999.14.1.0Data.GraphViz.Types.CanonicalDotGraph graphActionssymbols mkDestsMap mkNodeMap nodeToState fsmToFGL'fsmEdges symbolEdges syStateEdges syStateEdges' zipWithIndex mkActions mkDestSetEdgefsmEdgesParser edgesToFGL ppFsmEdgesfsmMatrixParserinterpretFsmMxppFsmMx fsmIOExtsrLookup tryLoadFsm