2 Finite Automata
  
  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 deterministic automaton (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 dense or complete. In the
  case of a non deterministic automaton (NFA) the entries of the matrix may be
  lists  of  non-negative integers. Automata with epsilon-transitions are also
  allowed:  the  last  letter  of the alphabet is assumed to be epsilon and is
  represented by @.
  
  
  2.1 Automata generation
  
  The way to create an automaton in GAP is the following
  
  2.1-1 Automaton
  
  > Automaton( Type, Size, Alphabet, TransitionTable, Initial, Accepting ) function
  
  Type  may be "det", "nondet" or "epsilon" according to whether the automaton
  is    deterministic,    non    deterministic    or    an    automaton   with
  epsilon-transitions.  Size  is a positive integer representing the number of
  states  of  the automaton. Alphabet is the number of letters of the alphabet
  or  a  list with the letters of the ordered alphabet. TransitionTable 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.  Initial  and Accepting are, respectively, the lists of initial and
  accepting states.
  
  ---------------------------  Example  ----------------------------
    
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,4]],[1],[4]);
    < deterministic automaton on 2 letters with 4 states >
    gap> Display(aut);
       |  1  2  3  4
    -----------------
     a |  3     3  4
     b |  3  4     4
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
    
  ------------------------------------------------------------------
  
  The alphabet of the automaton may be specified:
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,"01",[[3,,3,4],[3,4,0,4]],[1],[4]);
    < deterministic automaton on 2 letters with 4 states >
    gap> Display(aut);
       |  1  2  3  4
    -----------------
     0 |  3     3  4
     1 |  3  4     4
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
  ------------------------------------------------------------------
  
  Instead of leaving a hole in the transition matrix, we may write a 0 to mean
  that  no  transition is present. Non deterministic automata may be given the
  same way.
  
  ---------------------------  Example  ----------------------------
    gap> ndaut:=Automaton("nondet",4,2,[[3,[1,2],3,0],[3,4,0,[2,3]]],[1],[4]);
    < non deterministic automaton on 2 letters with 4 states >
    gap> Display(ndaut);
       |  1       2          3       4
    -----------------------------------------
     a | [ 3 ]   [ 1, 2 ]   [ 3 ]
     b | [ 3 ]   [ 4 ]              [ 2, 3 ]
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
  ------------------------------------------------------------------
  
  Also  in  the  same way can be given epsilon-automata. The letter epsilon is
  written @ instead.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("epsilon",3,"01@",[[,[2],[3]],[[1,3],,[1]],[[1],[2],
    > [2]]],[2],[2,3]);
    < epsilon automaton on 3 letters with 3 states >
    gap> Display(x);
       |  1          2       3
    ------------------------------
     0 |            [ 2 ]   [ 3 ]
     1 | [ 1, 3 ]           [ 1 ]
     @ | [ 1 ]      [ 2 ]   [ 2 ]
    Initial state:    [ 2 ]
    Accepting states: [ 2, 3 ]
  ------------------------------------------------------------------
  
  Bigger automata are displayed in another form:
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",16,2,[[4,0,0,6,3,1,4,8,7,4,3,0,6,1,6,0],
    > [3,4,0,0,6,1,0,6,1,6,1,6,6,4,8,7,4,5]],[1],[4]);
    < deterministic automaton on 2 letters with 16 states >
    gap> Display(aut);
    1    a   4
    1    b   3
    2    b   4
        ... some more lines
    15   a   6
    15   b   8
    16   b   7
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
  ------------------------------------------------------------------
  
  2.1-2 IsAutomaton
  
  > IsAutomaton( O ) _________________________________________________function
  
  In  the  presence  of  an  object  O,  one  may want to test whether O is an
  automaton. This may be done using the function IsAutomaton.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;
    gap> IsAutomaton(x);
    true
  ------------------------------------------------------------------
  
  2.1-3 IsDeterministicAutomaton
  
  > IsDeterministicAutomaton( aut ) __________________________________function
  
  Returns true when aut is a deterministic automaton and false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;
    gap> IsDeterministicAutomaton(x);
    true
  ------------------------------------------------------------------
  
  2.1-4 IsNonDeterministicAutomaton
  
  > IsNonDeterministicAutomaton( aut ) _______________________________function
  
  Returns true when aut is a non deterministic automaton and false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> y:=Automaton("nondet",3,2,[[,[1,3],],[,[2,3],[1,3]]],[1,2],[1,3]);;
    gap> IsNonDeterministicAutomaton(y);
    true
  ------------------------------------------------------------------
  
  2.1-5 IsEpsilonAutomaton
  
  > IsEpsilonAutomaton( aut ) ________________________________________function
  
  Returns true when aut is an epsilon-automaton and false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;
    gap> IsEpsilonAutomaton(z);
    true
  ------------------------------------------------------------------
  
  2.1-6 String
  
  > String( aut ) ____________________________________________________function
  
  The way GAP displays an automaton is quite natural, but when one wants to do
  small  changes, for example using copy/paste, the use of the function String
  (possibly followed by Print) may be usefull.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;
    gap> String(x);
    "Automaton(\"det\",3,\"ab\",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;"
    gap> Print(String(x));
    Automaton("det",3,"ab",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    gap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;
    gap> Print(String(z));
    Automaton("epsilon",2,"a@",[ [ [ 1, 2 ], [ ] ], [ [ 2 ], [ 1 ] ] ],[ 1, 2 ],[ \
    1, 2 ]);;
  ------------------------------------------------------------------
  
  2.1-7 RandomAutomaton
  
  > RandomAutomaton( Type, Size, Alphabet ) __________________________function
  
  Given  the  Type,  the  Size (i.e. the number of states) and the Alphabet (a
  positive  integer  or  a list), returns a pseudo random automaton with these
  parameters.
  
  ---------------------------  Example  ----------------------------
    gap> RandomAutomaton("det",5,"ac");
    < deterministic automaton on 2 letters with 5 states >
    gap> Display(last);
       |  1  2  3  4  5
    --------------------
     a |     2  3
     c |  2  3
    Initial state:    [ 4 ]
    Accepting states: [ 3, 4 ]
    
    gap> RandomAutomaton("nondet",3,["a","b","c"]);
    < non deterministic automaton on 3 letters with 3 states >
    
    gap> RandomAutomaton("epsilon",2,"abc");
    < epsilon automaton on 4 letters with 2 states >
    
    gap> RandomAutomaton("epsilon",2,2);
    < epsilon automaton on 3 letters with 2 states >
    gap> Display(last);
       |  1          2
    ----------------------
     a | [ 1, 2 ]
     b | [ 2 ]      [ 1 ]
     @ | [ 1, 2 ]
    Initial state:    [ 2 ]
    Accepting states: [ 1, 2 ]
    
    gap> a:=RandomTransformation(3);;
    gap> b:=RandomTransformation(3);;
    gap> aut:=RandomAutomaton("det",4,[a,b]);
    < deterministic automaton on 2 letters with 4 states >
  ------------------------------------------------------------------
  
  
  2.2 Automata internals
  
  In this section we describe the functions used to access the internals of an
  automaton.
  
  2.2-1 AlphabetOfAutomaton
  
  > AlphabetOfAutomaton( aut ) _______________________________________function
  
  Returns the number of symbols in the alphabet of automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> AlphabetOfAutomaton(aut);
    2
  ------------------------------------------------------------------
  
  2.2-2 AlphabetOfAutomatonAsList
  
  > AlphabetOfAutomatonAsList( aut ) _________________________________function
  
  Returns  the  alphabet of automaton aut 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 "abcd....". If the alphabet is
  given  by  means of an integer greater than 27, the function returns [ "a1",
  "a2", "a3", "a4", ... ].
  
  ---------------------------  Example  ----------------------------
    gap> a:=RandomAutomaton("det",5,"cat");
    < deterministic automaton on 3 letters with 5 states >
    gap> AlphabetOfAutomaton(a);
    3
    gap> AlphabetOfAutomatonAsList(a);
    "cat"
    gap> a:=RandomAutomaton("det",5,20);
    < deterministic automaton on 20 letters with 5 states >
    gap> AlphabetOfAutomaton(a);
    20
    gap> AlphabetOfAutomatonAsList(a);
    "abcdefghijklmnopqrst"
    gap> a:=RandomAutomaton("det",5,30);
    < deterministic automaton on 30 letters with 5 states >
    gap> AlphabetOfAutomaton(a);
    30
    gap> AlphabetOfAutomatonAsList(a);
    [ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", 
      "a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21",
      "a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ]
  ------------------------------------------------------------------
  
  2.2-3 TransitionMatrixOfAutomaton
  
  > TransitionMatrixOfAutomaton( aut ) _______________________________function
  
  Returns the transition matrix of automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> TransitionMatrixOfAutomaton(aut);
    [ [ 3, 0, 3, 4 ], [ 3, 4, 0, 0 ] ]
  ------------------------------------------------------------------
  
  2.2-4 InitialStatesOfAutomaton
  
  > InitialStatesOfAutomaton( aut ) __________________________________function
  
  Returns the initial states of automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> InitialStatesOfAutomaton(aut);
    [ 1 ]
  ------------------------------------------------------------------
  
  2.2-5 SetInitialStatesOfAutomaton
  
  > SetInitialStatesOfAutomaton( aut, I ) ____________________________function
  
  Sets  the  initial states of automaton aut. I may be a positive integer or a
  list of positive integers.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> SetInitialStatesOfAutomaton(aut,4);
    gap> InitialStatesOfAutomaton(aut);
    [ 4 ]
    gap> SetInitialStatesOfAutomaton(aut,[2,3]);
    gap> InitialStatesOfAutomaton(aut);
    [ 2, 3 ]
  ------------------------------------------------------------------
  
  2.2-6 FinalStatesOfAutomaton
  
  > FinalStatesOfAutomaton( aut ) ____________________________________function
  
  Returns the final states of automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> FinalStatesOfAutomaton(aut);
    [ 4 ]
  ------------------------------------------------------------------
  
  2.2-7 SetFinalStatesOfAutomaton
  
  > SetFinalStatesOfAutomaton( aut, F ) ______________________________function
  
  Sets  the  final  states  of automaton aut. F may be a positive integer or a
  list of positive integers.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> FinalStatesOfAutomaton(aut);
    [ 4 ]
    gap> SetFinalStatesOfAutomaton(aut,2);
    gap> FinalStatesOfAutomaton(aut);
    [ 2 ]
  ------------------------------------------------------------------
  
  2.2-8 NumberStatesOfAutomaton
  
  > NumberStatesOfAutomaton( aut ) ___________________________________function
  
  Returns the number of states of automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> NumberStatesOfAutomaton(aut);
    4
  ------------------------------------------------------------------
  
  
  2.3 Comparison of automata
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;
    gap> y:=Automaton("det",3,2,[ [ 2, 0, 0 ], [ 1, 3, 0 ] ],[ 3 ],[ 2, 3 ]);;
    gap> x=y;
    false
    gap> Size(Set([y,x,x]));
    2
  ------------------------------------------------------------------
  
  
  2.4 Tests involving automata
  
  This section describes some useful tests involving automata.
  
  2.4-1 IsDenseAutomaton
  
  > IsDenseAutomaton( aut ) __________________________________________function
  
  Tests   whether  a  deterministic  automaton  aut  is  complete.  (See  also
  NullCompletionAutomaton (2.5-2).)
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;
    gap> IsDenseAutomaton(aut);                                 
    false
  ------------------------------------------------------------------
  
  2.4-2 IsRecognizedByAutomaton
  
  > IsRecognizedByAutomaton( A, w ) __________________________________function
  
  The  argments  are:  an  automaton  A  and  a  string (i.e. a word) w in the
  alphabet  of  the  automaton.  Returns true if the word is recognized by the
  automaton and false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",3,2,[[1,2,1],[2,1,3]],[1],[2]);;
    gap> IsRecognizedByAutomaton(aut,"bbb");
    true
    
    gap> aut:=Automaton("det",3,"01",[[1,2,1],[2,1,3]],[1],[2]);;
    gap> IsRecognizedByAutomaton(aut,"111");
    true
  ------------------------------------------------------------------
  
  2.4-3 IsPermutationAutomaton
  
  > IsPermutationAutomaton( aut ) ____________________________________function
  
  The  argument is a deterministic automaton. Returns true when each letter of
  the alphabet induces a permutation on the vertices and false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 1, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;
    gap> IsPermutationAutomaton(x);
    true
  ------------------------------------------------------------------
  
  2.4-4 IsInverseAutomaton
  
  > IsInverseAutomaton( aut ) ________________________________________function
  
  The  argument is a deterministic automaton. Returns true when each letter of
  the alphabet induces an injective partial function on the vertices and false
  otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 1, 2 ] ],[ 2 ],[ 1 ]);;
    gap> IsInverseAutomaton(x);
    true
  ------------------------------------------------------------------
  
  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 AddInverseEdgesToInverseAutomaton
  
  2.4-5 AddInverseEdgesToInverseAutomaton
  
  > AddInverseEdgesToInverseAutomaton( aut ) _________________________function
  
  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.)
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[[ 0, 1, 3 ],[ 0, 1, 2 ]],[ 2 ],[ 1 ]);;Display(x);
       |  1  2  3
    --------------
     a |     1  3
     b |     1  2
    Initial state:   [ 2 ]
    Accepting state: [ 1 ]
    gap> AddInverseEdgesToInverseAutomaton(x);Display(x);
       |  1  2  3
    --------------
     a |     1  3
     b |     1  2
     A |  2     3
     B |  2  3
    Initial state:   [ 2 ]
    Accepting state: [ 1 ]
  ------------------------------------------------------------------
  
  2.4-6 IsReversibleAutomaton
  
  > IsReversibleAutomaton( aut ) _____________________________________function
  
  The  argument  is  a  deterministic  automaton.  Returns  true when aut is a
  reversible automaton, i.e. the automaton obtained by reversing all edges and
  switching  the initial and final states (see also ReversedAutomaton (2.5-5))
  is deterministic. Returns false otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 1, 2 ], [ 0, 1, 3 ] ],[ 2 ],[ 2 ]);;
    gap> IsReversibleAutomaton(x);
    true
  ------------------------------------------------------------------
  
  
  2.5 Basic operations
  
  2.5-1 CopyAutomaton
  
  > CopyAutomaton( aut ) _____________________________________________function
  
  Returns a new automaton, which is a copy of automaton aut.
  
  2.5-2 NullCompletionAutomaton
  
  > NullCompletionAutomaton( aut ) ___________________________________function
  
  aut  is  a deterministic automaton. If it is complete returns aut, otherwise
  returns  the  completion  (with  a null state) of aut. Notice that the words
  recognized by aut and its completion are the same.
  
  ---------------------------  Example  ----------------------------
    gap> aut:=Automaton("det",4,2,[[3,,3,4],[2,4,4,]],[1],[4]);;
    gap> IsDenseAutomaton(aut);
    false
    gap> y:=NullCompletionAutomaton(aut);;Display(y);
       |  1  2  3  4  5
    --------------------
     a |  3  5  3  4  5
     b |  2  4  4  5  5
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
  ------------------------------------------------------------------
  
  The  state  added  is a sink state 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.)
  
  2.5-3 ListSinkStatesAut
  
  > ListSinkStatesAut( aut ) _________________________________________function
  
  Computes the list of all sink states of the automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;
    gap> ListSinkStatesAut(x);
    [  ]
    gap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;
    gap> ListSinkStatesAut(y);
    [ 3 ]
  ------------------------------------------------------------------
  
  2.5-4 RemovedSinkStates
  
  > RemovedSinkStates( aut ) _________________________________________function
  
  Removes all sink states of the automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> y:=Automaton("det",3,2,[[ 2, 3, 3 ],[ 1, 2, 3 ]],[ 1 ],[ 2 ]);;Display(y);
       |  1  2  3
    --------------
     a |  2  3  3
     b |  1  2  3
    Initial state:   [ 1 ]
    Accepting state: [ 2 ]
    gap> x := RemovedSinkStates(y);Display(x);
    < deterministic automaton on 2 letters with 2 states >
       |  1  2
    -----------
     a |  2
     b |  1  2
    Initial state:   [ 1 ]
    Accepting state: [ 2 ]
  ------------------------------------------------------------------
  
  2.5-5 ReversedAutomaton
  
  > ReversedAutomaton( aut ) _________________________________________function
  
  Inverts the arrows of the automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;
    gap> z:=ReversedAutomaton(y);;Display(z);
       |  1       2       3
    ------------------------------
     a |         [ 1 ]   [ 2, 3 ]
     b | [ 1 ]   [ 2 ]   [ 3 ]
    Initial state:   [ 2 ]
    Accepting state: [ 1 ]
  ------------------------------------------------------------------
  
  2.5-6 PermutedAutomaton
  
  > PermutedAutomaton( aut, p ) ______________________________________function
  
  Given  an  automaton  aut  and  a  list  p representing a permutation of the
  states, outputs the equivalent permuted automaton.
  
  ---------------------------  Example  ----------------------------
    gap> y:=Automaton("det",4,2,[[2,3,4,2],[0,0,0,1]],[1],[3]);;Display(y);
       |  1  2  3  4
    -----------------
     a |  2  3  4  2
     b |           1
    Initial state:   [ 1 ]
    Accepting state: [ 3 ]
    gap> Display(PermutedAutomaton(y, [3,2,4,1]));
       |  1  2  3  4
    -----------------
     a |  2  4  2  1
     b |  3
    Initial state:   [ 3 ]
    Accepting state: [ 4 ]
  ------------------------------------------------------------------
  
  2.5-7 ListPermutedAutomata
  
  > ListPermutedAutomata( aut ) ______________________________________function
  
  Given an automaton aut, returns a list of automata with permuted states
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 0, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;
    gap> ListPermutedAutomata(x);
    [ < deterministic automaton on 2 letters with 3 states >, 
    < deterministic automaton on 2 letters with
        3 states >, < deterministic automaton on 2 letters with 3 states >,
      < deterministic automaton on 2 letters with 3 states >, 
    < deterministic automaton on 2 letters with
        3 states >, < deterministic automaton on 2 letters with 3 states > ]
  ------------------------------------------------------------------
  
  2.5-8 NormalizedAutomaton
  
  > NormalizedAutomaton( A ) _________________________________________function
  
  Produces  an equivalent automaton but in which the initial state is numbered
  1 and the accepting states have the greatest numbers.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[[ 1, 2, 0 ],[ 0, 1, 2 ]],[2],[1, 2]);;Display(x);
       |  1  2  3
    --------------
     a |  1  2
     b |     1  2
    Initial state:    [ 2 ]
    Accepting states: [ 1, 2 ]
    gap> Display(NormalizedAutomaton(x));
       |  1  2  3
    --------------
     a |  1     3
     b |  3  1
    Initial state:    [ 1 ]
    Accepting states: [ 3, 1 ]
  ------------------------------------------------------------------
  
  2.5-9 UnionAutomata
  
  > UnionAutomata( A, B ) ____________________________________________function
  
  Produces  the  disjoint  union  of  the  deterministic  or non deterministic
  automata A and B. The output is a non-deterministic automaton.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;
    gap> y:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 0, 0 ] ],[ 1 ],[ 1, 2, 3 ]);;
    gap> UnionAutomata(x,y);
    < non deterministic automaton on 2 letters with 6 states >
    gap> Display(last);
       |  1       2       3       4    5       6
    ------------------------------------------------
     a | [ 1 ]   [ 2 ]                [ 4 ]   [ 6 ]
     b |         [ 1 ]   [ 2 ]
    Initial states:   [ 2, 4 ]
    Accepting states: [ 1, 2, 4, 5, 6 ]
  ------------------------------------------------------------------
  
  2.5-10 ProductAutomaton
  
  > ProductAutomaton( A1, A2 ) _______________________________________function
  
  The  arguments must be deterministic automata. Returns the product of A1 and
  A2.
  
  Note:  (p,q)->(p-1)m+q  is  a  bijection  from  {1,...,  n}x  {1,...,  m} to
  {1,...,mn}.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",3,2);;Display(x);
       |  1  2  3
    --------------
     a |  2  3
     b |     1
    Initial state:    [ 3 ]
    Accepting states: [ 1, 2, 3 ]
    gap> y:=RandomAutomaton("det",3,2);;Display(y);
       |  1  2  3
    --------------
     a |     1
     b |  1  3
    Initial state:    [ 3 ]
    Accepting states: [ 1, 3 ]
    gap> z:=ProductAutomaton(x, y);;Display(z);
       |  1  2  3  4  5  6  7  8  9
    --------------------------------
     a |     4        7
     b |           1  3
    Initial state:    [ 9 ]
    Accepting states: [ 1, 3, 4, 6, 7, 9 ]
  ------------------------------------------------------------------
  
  2.5-11 ProductOfLanguages
  
  > ProductOfLanguages( A1, A2 ) _____________________________________function
  
  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.
  
  ---------------------------  Example  ----------------------------
    gap> a1:=ListOfWordsToAutomaton("ab",["aa","bb"]);
    < deterministic automaton on 2 letters with 5 states >
    gap> a2:=ListOfWordsToAutomaton("ab",["a","b"]);
    < deterministic automaton on 2 letters with 3 states >
    gap> ProductOfLanguages(a1,a2);
    < deterministic automaton on 2 letters with 5 states >
    gap> FAtoRatExp(last);
    (bbUaa)(aUb)
  ------------------------------------------------------------------
  
  
  2.6 Links with Semigroups
  
  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 transition semigroup of the automaton.
  
  2.6-1 TransitionSemigroup
  
  > TransitionSemigroup( aut ) _______________________________________function
  
  Returns the transition semigroup of the deterministic automaton aut.
  
  ---------------------------  Example  ----------------------------
    gap> aut := Automaton("det",10,2,[[7,5,7,5,4,9,10,9,10,9],
    > [8,6,8,9,9,1,3,1,9,9]],[2],[6,7,8,9,10]);;
    gap> s := TransitionSemigroup(aut);;       
    gap> Size(s);                                                                  
    30
  ------------------------------------------------------------------
  
  The  transition semigroup of the minimal automaton recognizing a language is
  the {\it syntactic semigroup} of that language.
  
  2.6-2 SyntacticSemigroupAut
  
  > SyntacticSemigroupAut( aut ) _____________________________________function
  
  Returns the syntactic semigroup of the deterministic automaton aut (i.e. the
  transition  semigroup  of  the  equivalent minimal automaton) when it is non
  empty and returns fail otherwise.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;
    gap> S:=SyntacticSemigroupAut(x);;
    gap> Size(S);
    3
  ------------------------------------------------------------------
  
  2.6-3 SyntacticSemigroupLang
  
  > SyntacticSemigroupLang( rat ) ____________________________________function
  
  Returns  the  syntactic  semigroup  of  the  language  given by the rational
  expression rat.
  
  ---------------------------  Example  ----------------------------
    gap> rat := RationalExpression("a*ba*ba*(@Ub)");;
    gap> S:=SyntacticSemigroupLang(rat);;
    gap> Size(S);
    7
  ------------------------------------------------------------------