  
  [1X2 Finite Automata[0X
  
  This  chapter  describes the representations used in this package for finite
  automata and some functions to determine information about them.
  
  We  have  to  remark  that  the  states  of  an  automaton  are always named
  1,2,3,...;  the  alphabet  may  be  given  by  the  user.  By  default it is
  {a,b,c,...} (or {a_1,a_2,a_3,...} in the case of alphabets with more than 27
  letters).
  
  The  transition function of an automaton with q states over an alphabet with
  n  letters is represented by a (not necessarily dense) nx q matrix. Each row
  of  the  matrix  describes  the  action  of  the corresponding letter on the
  states.  In  the  case of a [13Xdeterministic automaton[0m (DFA) the entries of the
  matrix  are  non-negative integers. When all entries of the transition table
  are positive integers, the automaton is said to be [13Xdense[0m or [13Xcomplete[0m. In the
  case of a [13Xnon deterministic automaton[0m (NFA) the entries of the matrix may be
  lists  of  non-negative integers. [13XAutomata with epsilon-transitions[0m are also
  allowed:  the  last  letter  of the alphabet is assumed to be epsilon and is
  represented by @.
  
  
  [1X2.1 Automata generation[0X
  
  The way to create an automaton in [5XGAP[0m is the following
  
  [1X2.1-1 Automaton[0m
  
  [2X> Automaton( [0X[3XType, Size, Alphabet, TransitionTable, Initial, Accepting[0X[2X ) [0Xfunction
  
  [10XType[0m  may be [10X"det"[0m, [10X"nondet"[0m or [10X"epsilon"[0m according to whether the automaton
  is    deterministic,    non    deterministic    or    an    automaton   with
  epsilon-transitions.  [10XSize[0m  is a positive integer representing the number of
  states  of  the automaton. [10XAlphabet[0m is the number of letters of the alphabet
  or  a  list with the letters of the ordered alphabet. [10XTransitionTable[0m is the
  transition  matrix.  The  entries are non-negative integers not greater than
  the  size of the automaton. In the case of non deterministic automata, lists
  of non-negative integers not greater than the size of the automaton are also
  allowed.  [10XInitial[0m  and [10XAccepting[0m are, respectively, the lists of initial and
  accepting states.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,4]],[1],[4]);[0X
    [4X< deterministic automaton on 2 letters with 4 states >[0X
    [4Xgap> Display(aut);[0X
    [4X   |  1  2  3  4[0X
    [4X-----------------[0X
    [4X a |  3     3  4[0X
    [4X b |  3  4     4[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 4 ][0X
    [4X[0X
  [4X------------------------------------------------------------------[0X
  
  The alphabet of the automaton may be specified:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,"01",[[3,,3,4],[3,4,0,4]],[1],[4]);[0X
    [4X< deterministic automaton on 2 letters with 4 states >[0X
    [4Xgap> Display(aut);[0X
    [4X   |  1  2  3  4[0X
    [4X-----------------[0X
    [4X 0 |  3     3  4[0X
    [4X 1 |  3  4     4[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  Instead of leaving a hole in the transition matrix, we may write a [10X0[0m to mean
  that  no  transition is present. Non deterministic automata may be given the
  same way.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> ndaut:=Automaton("nondet",4,2,[[3,[1,2],3,0],[3,4,0,[2,3]]],[1],[4]);[0X
    [4X< non deterministic automaton on 2 letters with 4 states >[0X
    [4Xgap> Display(ndaut);[0X
    [4X   |  1       2          3       4[0X
    [4X-----------------------------------------[0X
    [4X a | [ 3 ]   [ 1, 2 ]   [ 3 ][0X
    [4X b | [ 3 ]   [ 4 ]              [ 2, 3 ][0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  Also  in  the  same way can be given epsilon-automata. The letter epsilon is
  written [10X@[0m instead.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("epsilon",3,"01@",[[,[2],[3]],[[1,3],,[1]],[[1],[2],[0X
    [4X> [2]]],[2],[2,3]);[0X
    [4X< epsilon automaton on 3 letters with 3 states >[0X
    [4Xgap> Display(x);[0X
    [4X   |  1          2       3[0X
    [4X------------------------------[0X
    [4X 0 |            [ 2 ]   [ 3 ][0X
    [4X 1 | [ 1, 3 ]           [ 1 ][0X
    [4X @ | [ 1 ]      [ 2 ]   [ 2 ][0X
    [4XInitial state:    [ 2 ][0X
    [4XAccepting states: [ 2, 3 ][0X
  [4X------------------------------------------------------------------[0X
  
  Bigger automata are displayed in another form:
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",16,2,[[4,0,0,6,3,1,4,8,7,4,3,0,6,1,6,0],[0X
    [4X> [3,4,0,0,6,1,0,6,1,6,1,6,6,4,8,7,4,5]],[1],[4]);[0X
    [4X< deterministic automaton on 2 letters with 16 states >[0X
    [4Xgap> Display(aut);[0X
    [4X1    a   4[0X
    [4X1    b   3[0X
    [4X2    b   4[0X
    [4X    ... some more lines[0X
    [4X15   a   6[0X
    [4X15   b   8[0X
    [4X16   b   7[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-2 IsAutomaton[0m
  
  [2X> IsAutomaton( [0X[3XO[0X[2X ) _________________________________________________[0Xfunction
  
  In  the  presence  of  an  object  [3XO[0m,  one  may want to test whether [10XO[0m is an
  automaton. This may be done using the function [10XIsAutomaton[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X
    [4Xgap> IsAutomaton(x);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-3 IsDeterministicAutomaton[0m
  
  [2X> IsDeterministicAutomaton( [0X[3Xaut[0X[2X ) __________________________________[0Xfunction
  
  Returns [9Xtrue[0m when [10Xaut[0m is a deterministic automaton and [9Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X
    [4Xgap> IsDeterministicAutomaton(x);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-4 IsNonDeterministicAutomaton[0m
  
  [2X> IsNonDeterministicAutomaton( [0X[3Xaut[0X[2X ) _______________________________[0Xfunction
  
  Returns [9Xtrue[0m when [10Xaut[0m is a non deterministic automaton and [9Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> y:=Automaton("nondet",3,2,[[,[1,3],],[,[2,3],[1,3]]],[1,2],[1,3]);;[0X
    [4Xgap> IsNonDeterministicAutomaton(y);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-5 IsEpsilonAutomaton[0m
  
  [2X> IsEpsilonAutomaton( [0X[3Xaut[0X[2X ) ________________________________________[0Xfunction
  
  Returns [9Xtrue[0m when [10Xaut[0m is an epsilon-automaton and [9Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;[0X
    [4Xgap> IsEpsilonAutomaton(z);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-6 String[0m
  
  [2X> String( [0X[3Xaut[0X[2X ) ____________________________________________________[0Xfunction
  
  The way [5XGAP[0m displays an automaton is quite natural, but when one wants to do
  small  changes, for example using [13Xcopy/paste[0m, the use of the function [10XString[0m
  (possibly followed by [10XPrint[0m) may be usefull.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X
    [4Xgap> String(x);[0X
    [4X"Automaton(\"det\",3,\"ab\",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;"[0X
    [4Xgap> Print(String(x));[0X
    [4XAutomaton("det",3,"ab",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X
  [4X------------------------------------------------------------------[0X
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;[0X
    [4Xgap> Print(String(z));[0X
    [4XAutomaton("epsilon",2,"a@",[ [ [ 1, 2 ], [ ] ], [ [ 2 ], [ 1 ] ] ],[ 1, 2 ],[ \[0X
    [4X1, 2 ]);;[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.1-7 RandomAutomaton[0m
  
  [2X> RandomAutomaton( [0X[3XType, Size, Alphabet[0X[2X ) __________________________[0Xfunction
  
  Given  the  [3XType[0m,  the  [3XSize[0m (i.e. the number of states) and the [3XAlphabet[0m (a
  positive  integer  or  a list), returns a pseudo random automaton with these
  parameters.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> RandomAutomaton("det",5,"ac");[0X
    [4X< deterministic automaton on 2 letters with 5 states >[0X
    [4Xgap> Display(last);[0X
    [4X   |  1  2  3  4  5[0X
    [4X--------------------[0X
    [4X a |     2  3[0X
    [4X c |  2  3[0X
    [4XInitial state:    [ 4 ][0X
    [4XAccepting states: [ 3, 4 ][0X
    [4X[0X
    [4Xgap> RandomAutomaton("nondet",3,["a","b","c"]);[0X
    [4X< non deterministic automaton on 3 letters with 3 states >[0X
    [4X[0X
    [4Xgap> RandomAutomaton("epsilon",2,"abc");[0X
    [4X< epsilon automaton on 4 letters with 2 states >[0X
    [4X[0X
    [4Xgap> RandomAutomaton("epsilon",2,2);[0X
    [4X< epsilon automaton on 3 letters with 2 states >[0X
    [4Xgap> Display(last);[0X
    [4X   |  1          2[0X
    [4X----------------------[0X
    [4X a | [ 1, 2 ][0X
    [4X b | [ 2 ]      [ 1 ][0X
    [4X @ | [ 1, 2 ][0X
    [4XInitial state:    [ 2 ][0X
    [4XAccepting states: [ 1, 2 ][0X
    [4X[0X
    [4Xgap> a:=RandomTransformation(3);;[0X
    [4Xgap> b:=RandomTransformation(3);;[0X
    [4Xgap> aut:=RandomAutomaton("det",4,[a,b]);[0X
    [4X< deterministic automaton on 2 letters with 4 states >[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.2 Automata internals[0X
  
  In this section we describe the functions used to access the internals of an
  automaton.
  
  [1X2.2-1 AlphabetOfAutomaton[0m
  
  [2X> AlphabetOfAutomaton( [0X[3Xaut[0X[2X ) _______________________________________[0Xfunction
  
  Returns the number of symbols in the alphabet of automaton [10Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> AlphabetOfAutomaton(aut);[0X
    [4X2[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-2 AlphabetOfAutomatonAsList[0m
  
  [2X> AlphabetOfAutomatonAsList( [0X[3Xaut[0X[2X ) _________________________________[0Xfunction
  
  Returns  the  alphabet of automaton [10Xaut[0m always as a list. Note that when the
  alphabet  of  the  automaton  is  given as an integer (meaning the number of
  symbols)  less  than  27  it returns the list [10X"abcd...."[0m. If the alphabet is
  given  by  means of an integer greater than 27, the function returns [10X[ "a1",
  "a2", "a3", "a4", ... ][0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> a:=RandomAutomaton("det",5,"cat");[0X
    [4X< deterministic automaton on 3 letters with 5 states >[0X
    [4Xgap> AlphabetOfAutomaton(a);[0X
    [4X3[0X
    [4Xgap> AlphabetOfAutomatonAsList(a);[0X
    [4X"cat"[0X
    [4Xgap> a:=RandomAutomaton("det",5,20);[0X
    [4X< deterministic automaton on 20 letters with 5 states >[0X
    [4Xgap> AlphabetOfAutomaton(a);[0X
    [4X20[0X
    [4Xgap> AlphabetOfAutomatonAsList(a);[0X
    [4X"abcdefghijklmnopqrst"[0X
    [4Xgap> a:=RandomAutomaton("det",5,30);[0X
    [4X< deterministic automaton on 30 letters with 5 states >[0X
    [4Xgap> AlphabetOfAutomaton(a);[0X
    [4X30[0X
    [4Xgap> AlphabetOfAutomatonAsList(a);[0X
    [4X[ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", [0X
    [4X  "a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21",[0X
    [4X  "a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-3 TransitionMatrixOfAutomaton[0m
  
  [2X> TransitionMatrixOfAutomaton( [0X[3Xaut[0X[2X ) _______________________________[0Xfunction
  
  Returns the transition matrix of automaton [10Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> TransitionMatrixOfAutomaton(aut);[0X
    [4X[ [ 3, 0, 3, 4 ], [ 3, 4, 0, 0 ] ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-4 InitialStatesOfAutomaton[0m
  
  [2X> InitialStatesOfAutomaton( [0X[3Xaut[0X[2X ) __________________________________[0Xfunction
  
  Returns the initial states of automaton [10Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> InitialStatesOfAutomaton(aut);[0X
    [4X[ 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-5 SetInitialStatesOfAutomaton[0m
  
  [2X> SetInitialStatesOfAutomaton( [0X[3Xaut, I[0X[2X ) ____________________________[0Xfunction
  
  Sets  the  initial states of automaton [10Xaut[0m. [10XI[0m may be a positive integer or a
  list of positive integers.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> SetInitialStatesOfAutomaton(aut,4);[0X
    [4Xgap> InitialStatesOfAutomaton(aut);[0X
    [4X[ 4 ][0X
    [4Xgap> SetInitialStatesOfAutomaton(aut,[2,3]);[0X
    [4Xgap> InitialStatesOfAutomaton(aut);[0X
    [4X[ 2, 3 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-6 FinalStatesOfAutomaton[0m
  
  [2X> FinalStatesOfAutomaton( [0X[3Xaut[0X[2X ) ____________________________________[0Xfunction
  
  Returns the final states of automaton [10Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> FinalStatesOfAutomaton(aut);[0X
    [4X[ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-7 SetFinalStatesOfAutomaton[0m
  
  [2X> SetFinalStatesOfAutomaton( [0X[3Xaut, F[0X[2X ) ______________________________[0Xfunction
  
  Sets  the  final  states  of automaton [10Xaut[0m. [10XF[0m may be a positive integer or a
  list of positive integers.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> FinalStatesOfAutomaton(aut);[0X
    [4X[ 4 ][0X
    [4Xgap> SetFinalStatesOfAutomaton(aut,2);[0X
    [4Xgap> FinalStatesOfAutomaton(aut);[0X
    [4X[ 2 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.2-8 NumberStatesOfAutomaton[0m
  
  [2X> NumberStatesOfAutomaton( [0X[3Xaut[0X[2X ) ___________________________________[0Xfunction
  
  Returns the number of states of automaton [10Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> NumberStatesOfAutomaton(aut);[0X
    [4X4[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.3 Comparison of automata[0X
  
  Although  there  is  no standard way to compare automata it is usefull to be
  able  to  do  some  kind  of  comparison. Doing so, one can consider sets of
  automata. We just compare the strings of the automata.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X
    [4Xgap> y:=Automaton("det",3,2,[ [ 2, 0, 0 ], [ 1, 3, 0 ] ],[ 3 ],[ 2, 3 ]);;[0X
    [4Xgap> x=y;[0X
    [4Xfalse[0X
    [4Xgap> Size(Set([y,x,x]));[0X
    [4X2[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.4 Tests involving automata[0X
  
  This section describes some useful tests involving automata.
  
  [1X2.4-1 IsDenseAutomaton[0m
  
  [2X> IsDenseAutomaton( [0X[3Xaut[0X[2X ) __________________________________________[0Xfunction
  
  Tests   whether  a  deterministic  automaton  [10Xaut[0m  is  complete.  (See  also
  [2XNullCompletionAutomaton[0m ([14X2.5-2[0m).)
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X
    [4Xgap> IsDenseAutomaton(aut);                                 [0X
    [4Xfalse[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.4-2 IsRecognizedByAutomaton[0m
  
  [2X> IsRecognizedByAutomaton( [0X[3XA, w[0X[2X ) __________________________________[0Xfunction
  
  The  argments  are:  an  automaton  [3XA[0m  and  a  string (i.e. a word) [3Xw[0m in the
  alphabet  of  the  automaton.  Returns [10Xtrue[0m if the word is recognized by the
  automaton and [10Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",3,2,[[1,2,1],[2,1,3]],[1],[2]);;[0X
    [4Xgap> IsRecognizedByAutomaton(aut,"bbb");[0X
    [4Xtrue[0X
    [4X[0X
    [4Xgap> aut:=Automaton("det",3,"01",[[1,2,1],[2,1,3]],[1],[2]);;[0X
    [4Xgap> IsRecognizedByAutomaton(aut,"111");[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.4-3 IsPermutationAutomaton[0m
  
  [2X> IsPermutationAutomaton( [0X[3Xaut[0X[2X ) ____________________________________[0Xfunction
  
  The  argument is a deterministic automaton. Returns [9Xtrue[0m when each letter of
  the alphabet induces a permutation on the vertices and [9Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X
    [4Xgap> IsPermutationAutomaton(x);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.4-4 IsInverseAutomaton[0m
  
  [2X> IsInverseAutomaton( [0X[3Xaut[0X[2X ) ________________________________________[0Xfunction
  
  The  argument is a deterministic automaton. Returns [9Xtrue[0m when each letter of
  the alphabet induces an injective partial function on the vertices and [9Xfalse[0m
  otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 1, 2 ] ],[ 2 ],[ 1 ]);;[0X
    [4Xgap> IsInverseAutomaton(x);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  Frequently  an inverse automaton is thought as if the inverse edges (labeled
  by  formal  inverses  of the letters of the alphabet) were present, although
  they  are  usually  not  explicited.  They  can  be  made explicit using the
  function [10XAddInverseEdgesToInverseAutomaton[0m
  
  [1X2.4-5 AddInverseEdgesToInverseAutomaton[0m
  
  [2X> AddInverseEdgesToInverseAutomaton( [0X[3Xaut[0X[2X ) _________________________[0Xfunction
  
  The  argument is an inverse automaton over the alphabet {a,b,c,...}. Returns
  an  automaton  with the inverse edges added. (The formal inverse of a letter
  is represented by the corresponding capital letter.)
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[[ 0, 1, 3 ],[ 0, 1, 2 ]],[ 2 ],[ 1 ]);;Display(x);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |     1  3[0X
    [4X b |     1  2[0X
    [4XInitial state:   [ 2 ][0X
    [4XAccepting state: [ 1 ][0X
    [4Xgap> AddInverseEdgesToInverseAutomaton(x);Display(x);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |     1  3[0X
    [4X b |     1  2[0X
    [4X A |  2     3[0X
    [4X B |  2  3[0X
    [4XInitial state:   [ 2 ][0X
    [4XAccepting state: [ 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.4-6 IsReversibleAutomaton[0m
  
  [2X> IsReversibleAutomaton( [0X[3Xaut[0X[2X ) _____________________________________[0Xfunction
  
  The  argument  is  a  deterministic  automaton.  Returns  [9Xtrue[0m when [3Xaut[0m is a
  reversible automaton, i.e. the automaton obtained by reversing all edges and
  switching  the initial and final states (see also [2XReversedAutomaton[0m ([14X2.5-5[0m))
  is deterministic. Returns [9Xfalse[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 1, 2 ], [ 0, 1, 3 ] ],[ 2 ],[ 2 ]);;[0X
    [4Xgap> IsReversibleAutomaton(x);[0X
    [4Xtrue[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.5 Basic operations[0X
  
  [1X2.5-1 CopyAutomaton[0m
  
  [2X> CopyAutomaton( [0X[3Xaut[0X[2X ) _____________________________________________[0Xfunction
  
  Returns a new automaton, which is a copy of automaton [3Xaut[0m.
  
  [1X2.5-2 NullCompletionAutomaton[0m
  
  [2X> NullCompletionAutomaton( [0X[3Xaut[0X[2X ) ___________________________________[0Xfunction
  
  [10Xaut[0m  is  a deterministic automaton. If it is complete returns [3Xaut[0m, otherwise
  returns  the  completion  (with  a null state) of [3Xaut[0m. Notice that the words
  recognized by [3Xaut[0m and its completion are the same.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[2,4,4,]],[1],[4]);;[0X
    [4Xgap> IsDenseAutomaton(aut);[0X
    [4Xfalse[0X
    [4Xgap> y:=NullCompletionAutomaton(aut);;Display(y);[0X
    [4X   |  1  2  3  4  5[0X
    [4X--------------------[0X
    [4X a |  3  5  3  4  5[0X
    [4X b |  2  4  4  5  5[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  The  state  added  is a [13Xsink state[0m i.e. it is a state q which is not initial
  nor  accepting  and  for all letter a in the alphabet of the automaton, q is
  the  result  of  the action of a in q. (Notice that reading a word, one does
  not go out of a sink state.)
  
  [1X2.5-3 ListSinkStatesAut[0m
  
  [2X> ListSinkStatesAut( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction
  
  Computes the list of all sink states of the automaton [3Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X
    [4Xgap> ListSinkStatesAut(x);[0X
    [4X[  ][0X
    [4Xgap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;[0X
    [4Xgap> ListSinkStatesAut(y);[0X
    [4X[ 3 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-4 RemovedSinkStates[0m
  
  [2X> RemovedSinkStates( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction
  
  Removes all sink states of the automaton [3Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> y:=Automaton("det",3,2,[[ 2, 3, 3 ],[ 1, 2, 3 ]],[ 1 ],[ 2 ]);;Display(y);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |  2  3  3[0X
    [4X b |  1  2  3[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 2 ][0X
    [4Xgap> x := RemovedSinkStates(y);Display(x);[0X
    [4X< deterministic automaton on 2 letters with 2 states >[0X
    [4X   |  1  2[0X
    [4X-----------[0X
    [4X a |  2[0X
    [4X b |  1  2[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 2 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-5 ReversedAutomaton[0m
  
  [2X> ReversedAutomaton( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction
  
  Inverts the arrows of the automaton [3Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;[0X
    [4Xgap> z:=ReversedAutomaton(y);;Display(z);[0X
    [4X   |  1       2       3[0X
    [4X------------------------------[0X
    [4X a |         [ 1 ]   [ 2, 3 ][0X
    [4X b | [ 1 ]   [ 2 ]   [ 3 ][0X
    [4XInitial state:   [ 2 ][0X
    [4XAccepting state: [ 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-6 PermutedAutomaton[0m
  
  [2X> PermutedAutomaton( [0X[3Xaut, p[0X[2X ) ______________________________________[0Xfunction
  
  Given  an  automaton  [3Xaut[0m  and  a  list  [3Xp[0m representing a permutation of the
  states, outputs the equivalent permuted automaton.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> y:=Automaton("det",4,2,[[2,3,4,2],[0,0,0,1]],[1],[3]);;Display(y);[0X
    [4X   |  1  2  3  4[0X
    [4X-----------------[0X
    [4X a |  2  3  4  2[0X
    [4X b |           1[0X
    [4XInitial state:   [ 1 ][0X
    [4XAccepting state: [ 3 ][0X
    [4Xgap> Display(PermutedAutomaton(y, [3,2,4,1]));[0X
    [4X   |  1  2  3  4[0X
    [4X-----------------[0X
    [4X a |  2  4  2  1[0X
    [4X b |  3[0X
    [4XInitial state:   [ 3 ][0X
    [4XAccepting state: [ 4 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-7 ListPermutedAutomata[0m
  
  [2X> ListPermutedAutomata( [0X[3Xaut[0X[2X ) ______________________________________[0Xfunction
  
  Given an automaton [3Xaut[0m, returns a list of automata with permuted states
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X
    [4Xgap> ListPermutedAutomata(x);[0X
    [4X[ < deterministic automaton on 2 letters with 3 states >, [0X
    [4X< deterministic automaton on 2 letters with[0X
    [4X    3 states >, < deterministic automaton on 2 letters with 3 states >,[0X
    [4X  < deterministic automaton on 2 letters with 3 states >, [0X
    [4X< deterministic automaton on 2 letters with[0X
    [4X    3 states >, < deterministic automaton on 2 letters with 3 states > ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-8 NormalizedAutomaton[0m
  
  [2X> NormalizedAutomaton( [0X[3XA[0X[2X ) _________________________________________[0Xfunction
  
  Produces  an equivalent automaton but in which the initial state is numbered
  1 and the accepting states have the greatest numbers.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[[ 1, 2, 0 ],[ 0, 1, 2 ]],[2],[1, 2]);;Display(x);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |  1  2[0X
    [4X b |     1  2[0X
    [4XInitial state:    [ 2 ][0X
    [4XAccepting states: [ 1, 2 ][0X
    [4Xgap> Display(NormalizedAutomaton(x));[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |  1     3[0X
    [4X b |  3  1[0X
    [4XInitial state:    [ 1 ][0X
    [4XAccepting states: [ 3, 1 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-9 UnionAutomata[0m
  
  [2X> UnionAutomata( [0X[3XA, B[0X[2X ) ____________________________________________[0Xfunction
  
  Produces  the  disjoint  union  of  the  deterministic  or non deterministic
  automata [10XA[0m and [10XB[0m. The output is a non-deterministic automaton.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;[0X
    [4Xgap> y:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 0, 0 ] ],[ 1 ],[ 1, 2, 3 ]);;[0X
    [4Xgap> UnionAutomata(x,y);[0X
    [4X< non deterministic automaton on 2 letters with 6 states >[0X
    [4Xgap> Display(last);[0X
    [4X   |  1       2       3       4    5       6[0X
    [4X------------------------------------------------[0X
    [4X a | [ 1 ]   [ 2 ]                [ 4 ]   [ 6 ][0X
    [4X b |         [ 1 ]   [ 2 ][0X
    [4XInitial states:   [ 2, 4 ][0X
    [4XAccepting states: [ 1, 2, 4, 5, 6 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-10 ProductAutomaton[0m
  
  [2X> ProductAutomaton( [0X[3XA1, A2[0X[2X ) _______________________________________[0Xfunction
  
  The  arguments must be deterministic automata. Returns the product of [3XA1[0m and
  [3XA2[0m.
  
  Note:  (p,q)->(p-1)m+q  is  a  bijection  from  {1,...,  n}x  {1,...,  m} to
  {1,...,mn}.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=RandomAutomaton("det",3,2);;Display(x);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |  2  3[0X
    [4X b |     1[0X
    [4XInitial state:    [ 3 ][0X
    [4XAccepting states: [ 1, 2, 3 ][0X
    [4Xgap> y:=RandomAutomaton("det",3,2);;Display(y);[0X
    [4X   |  1  2  3[0X
    [4X--------------[0X
    [4X a |     1[0X
    [4X b |  1  3[0X
    [4XInitial state:    [ 3 ][0X
    [4XAccepting states: [ 1, 3 ][0X
    [4Xgap> z:=ProductAutomaton(x, y);;Display(z);[0X
    [4X   |  1  2  3  4  5  6  7  8  9[0X
    [4X--------------------------------[0X
    [4X a |     4        7[0X
    [4X b |           1  3[0X
    [4XInitial state:    [ 9 ][0X
    [4XAccepting states: [ 1, 3, 4, 6, 7, 9 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.5-11 ProductOfLanguages[0m
  
  [2X> ProductOfLanguages( [0X[3XA1, A2[0X[2X ) _____________________________________[0Xfunction
  
  Given  two  regular languages (as automata or rational expressions), returns
  an  automaton that recognizes the concatenation of the given languages, that
  is,  the  set  of  words  uv such that u belongs to the first language and v
  belongs to the second language.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> a1:=ListOfWordsToAutomaton("ab",["aa","bb"]);[0X
    [4X< deterministic automaton on 2 letters with 5 states >[0X
    [4Xgap> a2:=ListOfWordsToAutomaton("ab",["a","b"]);[0X
    [4X< deterministic automaton on 2 letters with 3 states >[0X
    [4Xgap> ProductOfLanguages(a1,a2);[0X
    [4X< deterministic automaton on 2 letters with 5 states >[0X
    [4Xgap> FAtoRatExp(last);[0X
    [4X(bbUaa)(aUb)[0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X2.6 Links with Semigroups[0X
  
  Each letter of the alphabet of an automaton induces a partial transformation
  in  its  set  of states. The semigroup generated by these transformations is
  called the [13Xtransition semigroup[0m of the automaton.
  
  [1X2.6-1 TransitionSemigroup[0m
  
  [2X> TransitionSemigroup( [0X[3Xaut[0X[2X ) _______________________________________[0Xfunction
  
  Returns the transition semigroup of the deterministic automaton [3Xaut[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> aut := Automaton("det",10,2,[[7,5,7,5,4,9,10,9,10,9],[0X
    [4X> [8,6,8,9,9,1,3,1,9,9]],[2],[6,7,8,9,10]);;[0X
    [4Xgap> s := TransitionSemigroup(aut);;       [0X
    [4Xgap> Size(s);                                                                  [0X
    [4X30[0X
  [4X------------------------------------------------------------------[0X
  
  The  transition semigroup of the minimal automaton recognizing a language is
  the {\it syntactic semigroup} of that language.
  
  [1X2.6-2 SyntacticSemigroupAut[0m
  
  [2X> SyntacticSemigroupAut( [0X[3Xaut[0X[2X ) _____________________________________[0Xfunction
  
  Returns the syntactic semigroup of the deterministic automaton [3Xaut[0m (i.e. the
  transition  semigroup  of  the  equivalent minimal automaton) when it is non
  empty and returns [9Xfail[0m otherwise.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;[0X
    [4Xgap> S:=SyntacticSemigroupAut(x);;[0X
    [4Xgap> Size(S);[0X
    [4X3[0X
  [4X------------------------------------------------------------------[0X
  
  [1X2.6-3 SyntacticSemigroupLang[0m
  
  [2X> SyntacticSemigroupLang( [0X[3Xrat[0X[2X ) ____________________________________[0Xfunction
  
  Returns  the  syntactic  semigroup  of  the  language  given by the rational
  expression [3Xrat[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> rat := RationalExpression("a*ba*ba*(@Ub)");;[0X
    [4Xgap> S:=SyntacticSemigroupLang(rat);;[0X
    [4Xgap> Size(S);[0X
    [4X7[0X
  [4X------------------------------------------------------------------[0X
  
