chap5.txt

  
  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 ϵ-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 ϵ-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  ϵ-transitions.  Returns  an  ϵNFA  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 ϵ-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 ]