5 Some functions involving automata
  
  This  chapter  describes  some  functions involving automata. It starts with
  functions   to   obtain   equivalent   automata  of  other  type.  Then  the
  minimalization is considered.
  
  
  5.1 From one type to another
  
  Recall  that  two automata are said to be equivalent when they recognize the
  same  language.  Next  we have functions which have as input automata of one
  type and as output equivalent automata of another type.
  
  5.1-1 EpsilonToNFA
  
  > EpsilonToNFA( A ) ________________________________________________function
  
  A  is  an  automaton with epsilon-transitions. Returns a NFA recognizing the
  same language.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("epsilon",3,2);;Display(x);
       |  1          2          3
    ------------------------------------
     a | [ 2 ]      [ 3 ]      [ 2 ]
     b | [ 1, 2 ]   [ 1, 2 ]   [ 1, 3 ]
     @ | [ 1, 2 ]   [ 1, 2 ]   [ 1, 2 ]
    Initial states:   [ 2, 3 ]
    Accepting states: [ 1, 2, 3 ]
    gap> Display(EpsilonToNFA(x));
       |  1          2             3
    ------------------------------------------
     a | [ 1, 2 ]   [ 1, 2, 3 ]   [ 1, 2 ]
     b | [ 1, 2 ]   [ 1, 2 ]      [ 1, 2, 3 ]
    Initial states:   [ 1, 2, 3 ]
    Accepting states: [ 1, 2, 3 ]
  ------------------------------------------------------------------
  
  5.1-2 EpsilonToNFASet
  
  > EpsilonToNFASet( A ) _____________________________________________function
  
  A  is  an  automaton with epsilon-transitions. Returns a NFA recognizing the
  same language. This function differs from EpsilonToNFA (5.1-1) in that it is
  faster  for  smaller automata, or automata with few epsilon transitions, but
  slower in the really hard cases.
  
  5.1-3 EpsilonCompactedAut
  
  > EpsilonCompactedAut( A ) _________________________________________function
  
  A  is an automaton with epsilon-transitions. Returns an epsilonNFA with each
  strongly-connected   component  of  the  epsilon-transitions  digraph  of  A
  identified with a single state and recognizing the same language.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("epsilon",3,2);;Display(x);
       |  1          2          3
    ------------------------------------
     a | [ 1, 2 ]   [ 1, 3 ]   [ 1, 2 ]
     b | [ 1, 2 ]   [ 1, 2 ]   [ 2, 3 ]
     @ |            [ 3 ]      [ 2 ]
    Initial state:    [ 3 ]
    Accepting states: [ 1, 3 ]
    gap> Display(EpsilonCompactedAut(x));
       |  1          2
    -------------------------
     a | [ 1, 2 ]   [ 1, 2 ]
     b | [ 1, 2 ]   [ 1, 2 ]
     @ |
    Initial state:    [ 2 ]
    Accepting states: [ 1, 2 ]
  ------------------------------------------------------------------
  
  5.1-4 ReducedNFA
  
  > ReducedNFA( A ) __________________________________________________function
  
  A is a non deterministic automaton (without epsilon-transitions). Returns an
  NFA  accepting the same language as its input but with possibly fewer states
  (it  quotients out by the smallest right-invariant partition of the states).
  A paper describing the algorithm is in preparation.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("nondet",5,2);;Display(x);
       |  1             2                3             4             5
    ----------------------------------------------------------------------
     a | [ 1, 5 ]      [ 1, 2, 4, 5 ]   [ 1, 3, 5 ]   [ 3, 4, 5 ]   [ 4 ]
     b | [ 2, 3, 4 ]   [ 3 ]            [ 2, 3, 4 ]   [ 2, 4, 5 ]   [ 3 ]
    Initial state:    [ 4 ]
    Accepting states: [ 1, 3, 4, 5 ]
    gap> Display(ReducedNFA(x));
       |  1             2                3       4
    --------------------------------------------------------
     a | [ 1, 3 ]      [ 1, 2, 3, 4 ]   [ 4 ]   [ 1, 3, 4 ]
     b | [ 1, 2, 4 ]   [ 1 ]            [ 1 ]   [ 2, 3, 4 ]
    Initial state:    [ 4 ]
    Accepting states: [ 1, 3, 4 ]
  ------------------------------------------------------------------
  
  5.1-5 NFAtoDFA
  
  > NFAtoDFA( A ) ____________________________________________________function
  
  Given an NFA, these synonym functions, compute the equivalent DFA, using the
  powerset construction, according to the algorithm presented in the report of
  the AMoRE [MMPTV95] program. The returned automaton is dense deterministic
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("nondet",3,2);;Display(x);
       |  1       2    3
    ---------------------------
     a | [ 2 ]        [ 1, 3 ]
     b |              [ 2, 3 ]
    Initial states:   [ 1, 3 ]
    Accepting states: [ 1, 2 ]
    gap> Display(NFAtoDFA(x));
       |  1  2  3
    --------------
     a |  2  2  1
     b |  3  3  3
    Initial state:    [ 1 ]
    Accepting states: [ 1, 2, 3 ]
  ------------------------------------------------------------------
  
  5.1-6 FuseSymbolsAut
  
  > FuseSymbolsAut( A, s1, s2 ) ______________________________________function
  
  Given  an  automaton A and integers s1 and s2 which, returns an NFA obtained
  by replacing all transitions through s2 by transitions through s1.
  
  ---------------------------  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> Display(FuseSymbolsAut(x,1,2));
       |  1       2          3
    ---------------------------
     a | [ 2 ]   [ 1, 3 ]
    Initial state:    [ 3 ]
    Accepting states: [ 1, 2, 3 ]
  ------------------------------------------------------------------
  
  
  5.2 Minimalization of an automaton
  
  The  algorithm  used to minimalize a dense deterministic automaton (i.e., to
  compute a dense minimal automaton recognizing the same language) is based on
  an  algorithm  due  to Hopcroft (see [AHU74]). It is well known (see [HU69])
  that  it  suffices to reduce the automaton given and remove the inaccessible
  states.  Again,  the  documentation for the computer program AMoRE [MMPTV95]
  has been very useful.
  
  5.2-1 UsefulAutomaton
  
  > UsefulAutomaton( A ) _____________________________________________function
  
  Given  an  automaton  A  (deterministic or not), outputs a dense DFA B whose
  states are all reachable and such that A and B are equivalent.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",4,2);;Display(x);
       |  1  2  3  4
    -----------------
     a |     3  4
     b |  1  4
    Initial state:    [ 3 ]
    Accepting states: [ 2, 3, 4 ]
    gap> Display(UsefulAutomaton(x));
       |  1  2  3
    --------------
     a |  2  3  3
     b |  3  3  3
    Initial state:    [ 1 ]
    Accepting states: [ 1, 2 ]
  ------------------------------------------------------------------
  
  5.2-2 MinimalizedAut
  
  > MinimalizedAut( A ) ______________________________________________function
  
  Returns the minimal automaton equivalent to A.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",4,2);;Display(x);
       |  1  2  3  4
    -----------------
     a |     3  4
     b |  1  2  3
    Initial state:    [ 4 ]
    Accepting states: [ 2, 3, 4 ]
    gap> Display(MinimalizedAut(x));
       |  1  2
    -----------
     a |  2  2
     b |  2  2
    Initial state:   [ 1 ]
    Accepting state: [ 1 ]
  ------------------------------------------------------------------
  
  5.2-3  MinimalAutomaton
  
  >  MinimalAutomaton( A ) __________________________________________attribute
  
  Returns  the minimal automaton equivalent to A, but stores it so that future
  computations of this automaton just return the stored automaton.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",4,2);;Display(x);
       |  1  2  3  4
    -----------------
     a |     2  4
     b |     3  4
    Initial state:    [ 4 ]
    Accepting states: [ 1, 2, 3 ]
    gap> Display(MinimalAutomaton(x));
       |  1
    --------
     a |  1
     b |  1
    Initial state:   [ 1 ]
    Accepting state:
  ------------------------------------------------------------------
  
  5.2-4 AccessibleStates
  
  > AccessibleStates( aut[, p] ) _____________________________________function
  
  Computes  the  list of states of the automaton aut which are accessible from
  state  p.  When p is not given, returns the states which are accessible from
  any initial state.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",4,2);;Display(x);
       |  1  2  3  4
    -----------------
     a |     1  2  4
     b |     2  4
    Initial state:    [ 2 ]
    Accepting states: [ 1, 2, 3 ]
    gap> AccessibleStates(x,3);
    [ 1, 2, 3, 4 ]
  ------------------------------------------------------------------
  
  5.2-5 AccessibleAutomaton
  
  > AccessibleAutomaton( A ) _________________________________________function
  
  If  A  is  a  deterministic  automaton, not necessarily dense, an equivalent
  dense   deterministic   accessible  automaton  is  returned.  (The  function
  UsefulAutomaton is called.)
  
  If  A  is  not  deterministic  with  a  single  initial state, an equivalent
  accessible automaton is returned.
  
  ---------------------------  Example  ----------------------------
    gap> x:=RandomAutomaton("det",4,2);;Display(x);
       |  1  2  3  4
    -----------------
     a |  1  3
     b |  1  3  4
    Initial state:    [ 2 ]
    Accepting states: [ 3, 4 ]
    gap> Display(AccessibleAutomaton(x));
       |  1  2  3  4
    -----------------
     a |  2  4  4  4
     b |  2  3  4  4
    Initial state:    [ 1 ]
    Accepting states: [ 2, 3 ]
  ------------------------------------------------------------------
  
  5.2-6 IntersectionLanguage
  
  > IntersectionLanguage( A1, A2 ) ___________________________________function
  > IntersectionAutomaton( A1, A2 ) __________________________________function
  
  Computes  an  automaton  that  recognizes  the intersection of the languages
  given  (through  automata  or  rational  expressions by) A1 and A2. When the
  arguments  are  deterministic automata, is the same as ProductAutomaton, but
  works  for  all  kinds of automata. Note that the language of the product of
  two automata is precisely the intersection of the languages of the automata.
  
  ---------------------------  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> Display(IntersectionLanguage(x,y));
       |  1  2
    -----------
     a |  2  2
     b |  2  2
    Initial state:   [ 1 ]
    Accepting state: [ 1 ]
  ------------------------------------------------------------------
  
  5.2-7 AutomatonAllPairsPaths
  
  > AutomatonAllPairsPaths( A ) ______________________________________function
  
  Given  an  automaton  A,  with n states, outputs a n x n matrix P, such that
  P[i][j] is the list of simple paths from state i to state j in A.
  
  ---------------------------  Example  ----------------------------
    gap> a:=RandomAutomaton("det",3,2);
    < deterministic automaton on 2 letters with 3 states >
    gap> AutomatonAllPairsPaths(a);
    [ [ [ [ 1, 1 ] ], [  ], [  ] ], [ [ [ 2, 1 ] ], [ [ 2, 2 ] ], [  ] ],
      [ [ [ 3, 2, 1 ] ], [ [ 3, 2 ] ], [ [ 3, 3 ] ] ] ]
    gap> Display(a);
       |  1  2  3
    --------------
     a |     1  2
     b |  1  2  3
    Initial state:    [ 3 ]
    Accepting states: [ 1, 2 ]
  ------------------------------------------------------------------