chap2.txt

  
  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 26
  letters).
  
  The  transition function of an automaton with q states over an alphabet with
  n  letters is represented by a (not necessarily dense) n× 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  ϵ-transitions  are  also
  allowed:  the  last  letter  of  the  alphabet  is  assumed  to  be ϵ 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 ϵ-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 ϵ-automata. The letter ϵ 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 ϵ-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) not greater than 26 it returns the list "abcd....". If the alphabet
  is  given  by  means  of  an integer greater than 26, 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  arguments  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}×  {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