4 Automata versus rational expressions
  
  A  remarkable theorem due to Kleene shows that a language is recognized by a
  finite  automaton  precisely  when  it  may  be given by means of a rational
  expression, i.e. is a rational language.
  
  An  automaton  and a rational expression are said to be equivalent when both
  represent  the  same  language.  In this chapter we describe functions to go
  from automata to equivalent rational expressions and vice-versa.
  
  
  4.1 From automata to rational expressions
  
  4.1-1 AutomatonToRatExp 
  
  > AutomatonToRatExp ( A ) __________________________________________function
  > AutToRatExp( A ) _________________________________________________function
  > FAtoRatExp( A ) __________________________________________________function
  
  From  a  finite  automaton,  FAtoRatExp,  AutToRatExp and AutomatonToRatExp,
  which  are  synonyms,  compute one equivalent rational expression, using the
  state elimination algorithm.
  
  ---------------------------  Example  ----------------------------
    gap> x:=Automaton("det",4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;
    gap> FAtoRatExp(x);
    (aUb)(aUb)U@
    gap> aut:=Automaton("det",4,"xy",[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;
    gap> FAtoRatExp(aut);                                                                
    (xUy)(xUy)U@
  ------------------------------------------------------------------
  
  
  4.2 From rational expression to automata
  
  4.2-1 RatExpToNDAut
  
  > RatExpToNDAut( R ) _______________________________________________function
  
  Given a rational expression R, computes the equivalent NFA
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("aUab");
    aUab
    gap> Display(RatExpToNDAut(r));
       |  1    2       3    4
    --------------------------------
     a |                   [ 1, 2 ]
     b |      [ 3 ]
    Initial state:    [ 4 ]
    Accepting states: [ 1, 3 ]
    gap> r:=RationalExpression("xUxy"); 
    xUxy
    gap> Display(RatExpToNDAut(r));    
       |  1    2       3    4
    --------------------------------
     x |                   [ 1, 2 ]   
     y |      [ 3 ]                   
    Initial state:    [ 4 ]
    Accepting states: [ 1, 3 ]
  ------------------------------------------------------------------
  
  4.2-2 RatExpToAutomaton
  
  > RatExpToAutomaton( R ) ___________________________________________function
  > RatExpToAut( R ) _________________________________________________function
  
  Given  a  rational  expression  R,  these functions, which are synonyms, use
  RatExpToNDAut  (4.2-1))  to  compute the equivalent NFA and then returns the
  equivalent minimal DFA
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("@U(aUb)(aUb)");
    @U(aUb)(aUb)
    gap> Display(RatExpToAut(r));
       |  1  2  3  4
    -----------------
     a |  3  1  3  2
     b |  3  1  3  2
    Initial state:    [ 4 ]
    Accepting states: [ 1, 4 ]
    gap> r:=RationalExpression("@U(0U1)(0U1)");
    @U(0U1)(0U1)
    gap> Display(RatExpToAut(r));              
       |  1  2  3  4  
    -----------------
     0 |  3  1  3  2  
     1 |  3  1  3  2  
    Initial state:    [ 4 ]
    Accepting states: [ 1, 4 ]
  ------------------------------------------------------------------
  
  
  4.3 Some tests on automata
  
  This  section  describes  functions that perform tests on automata, rational
  expressions and their accepted languages.
  
  4.3-1 IsEmptyLang
  
  > IsEmptyLang( R ) _________________________________________________function
  
  This  function  tests if the language given through a rational expression or
  an automaton  R  is the empty language.
  
  ---------------------------  Example  ----------------------------
    gap> r:=RandomRatExp(2);
    empty_set
    gap> IsEmptyLang(r);
    true
    gap> r:=RandomRatExp(2);
    aUb
    gap> IsEmptyLang(r);
    false
  ------------------------------------------------------------------
  
  4.3-2 IsFullLang
  
  > IsFullLang( R ) __________________________________________________function
  
  This  function  tests if the language given through a rational expression or
  an automaton  R  represents the Kleene closure of the alphabet of  R  .
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("aUb");
    aUb
    gap> IsFullLang(r);
    false
    gap> r:=RationalExpression("(aUb)*");
    (aUb)*
    gap> IsFullLang(r);
    true
  ------------------------------------------------------------------
  
  4.3-3 AreEqualLang
  
  > AreEqualLang( A1, A2 ) ___________________________________________function
  > AreEquivAut( A1, A2 ) ____________________________________________function
  
  These  functions,  which  are  synonyms,  test  if  the automata or rational
  expressions A1 and A2 are equivalent, i.e. represent the same language. This
  is  performed  by  checking  that  the  corresponding  minimal  automata are
  isomorphic. Note hat this cannot happen if the alphabets are different.
  
  ---------------------------  Example  ----------------------------
    gap> y:=RandomAutomaton("det",4,2);;
    gap> x:=RandomAutomaton("det",4,2);;
    gap> AreEquivAut(x, y);
    false
    gap> a:=RationalExpression("(aUb)*ab*");
    (aUb)*ab*
    gap> b:=RationalExpression("(aUb)*");
    (aUb)*
    gap> AreEqualLang(a, b);
    false
    gap> a:=RationalExpression("(bUa)*");
    (bUa)*
    gap> AreEqualLang(a, b);
    true
    gap> x:=RationalExpression("(1U0)*");
    (1U0)*
    gap> AreEqualLang(a, x);  
    The given languages are not over the same alphabet
    false
    g
  ------------------------------------------------------------------
  
  4.3-4 IsContainedLang
  
  > IsContainedLang( R1, R2 ) ________________________________________function
  
  Tests  if  the  language  represented  (through  an  automaton or a rational
  expression)  by    R1   is contained in the language represented (through an
  automaton or a rational expression) by  R2  .
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("aUab");
    aUab
    gap> s:=RationalExpression("a","ab");
    a
    gap> IsContainedLang(s,r);
    true
    gap> IsContainedLang(r,s);
    false
  ------------------------------------------------------------------
  
  4.3-5 AreDisjointLang
  
  > AreDisjointLang( R1, R2 ) ________________________________________function
  
  Tests   if  the  languages  represented  (through  automata  or  a  rational
  expressions) by  R1  and  R2  are disjoint.
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("aUab");;
    gap> s:=RationalExpression("a","ab");;
    gap> AreDisjointLang(r,s);
    false
  ------------------------------------------------------------------