  
  [1m[4m[31m4. Automata [22m[36mversus[1m[4m[31m rational expressions[0m
  
  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 [22m[36mequivalent[0m when both
  represent  the  same  language.  In this chapter we describe functions to go
  from automata to equivalent rational expressions and [22m[36mvice-versa[0m.
  
  
  [1m[4m[31m4.1 From automata to rational expressions[0m
  
  [1m[4m[31m4.1-1 AutomatonToRatExp [0m
  
  [1m[34m> AutomatonToRatExp ( [0m[22m[34mA[0m[1m[34m ) __________________________________________[0mfunction
  [1m[34m> AutToRatExp( [0m[22m[34mA[0m[1m[34m ) _________________________________________________[0mfunction
  [1m[34m> FAtoRatExp( [0m[22m[34mA[0m[1m[34m ) __________________________________________________[0mfunction
  
  From  a  finite  automaton,  [22m[32mFAtoRatExp[0m,  [22m[32mAutToRatExp[0m and [22m[32mAutomatonToRatExp[0m,
  which  are  synonyms,  compute one equivalent rational expression, using the
  state elimination algorithm.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> x:=Automaton("det",4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;[0m
    [22m[35mgap> FAtoRatExp(x);[0m
    [22m[35m(aUb)(aUb)U@[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m4.2 From rational expression to automata[0m
  
  [1m[4m[31m4.2-1 RatExpToNDAut[0m
  
  [1m[34m> RatExpToNDAut( [0m[22m[34mR[0m[1m[34m ) _______________________________________________[0mfunction
  
  Given a rational expression [22m[34mR[0m, computes the equivalent NFA
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RationalExpression("aUab");[0m
    [22m[35maUab[0m
    [22m[35mgap> Display(RatExpToNDAut(r));[0m
    [22m[35m   |  1    2       3    4[0m
    [22m[35m--------------------------------[0m
    [22m[35m a |                   [ 1, 2 ][0m
    [22m[35m b |      [ 3 ][0m
    [22m[35mInitial state:    [ 4 ][0m
    [22m[35mAccepting states: [ 1, 3 ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.2-2 RatExpToAutomaton[0m
  
  [1m[34m> RatExpToAutomaton( [0m[22m[34mR[0m[1m[34m ) ___________________________________________[0mfunction
  [1m[34m> RatExpToAut( [0m[22m[34mR[0m[1m[34m ) _________________________________________________[0mfunction
  
  Given  a  rational  expression  [22m[34mR[0m,  these functions, which are synonyms, use
  [1m[34mRatExpToNDAut[0m  ([1m4.2-1[0m))  to  compute the equivalent NFA and then returns the
  equivalent minimal DFA
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RationalExpression("@U(aUb)(aUb)");[0m
    [22m[35m@U(aUb)(aUb)[0m
    [22m[35mgap> Display(RatExpToAut(r));[0m
    [22m[35m   |  1  2  3  4[0m
    [22m[35m-----------------[0m
    [22m[35m a |  3  1  3  2[0m
    [22m[35m b |  3  1  3  2[0m
    [22m[35mInitial state:    [ 4 ][0m
    [22m[35mAccepting states: [ 1, 4 ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m4.3 Some tests on automata[0m
  
  This  section  describes  functions that perform tests on automata, rational
  expressions and their accepted languages.
  
  [1m[4m[31m4.3-1 IsEmptyLang[0m
  
  [1m[34m> IsEmptyLang( [0m[22m[34mR[0m[1m[34m ) _________________________________________________[0mfunction
  
  This  function  tests if the language given through a rational expression or
  an automaton [22m[34m R [0m is the empty language.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RandomRatExp(2);[0m
    [22m[35mempty_set[0m
    [22m[35mgap> IsEmptyLang(r);[0m
    [22m[35mtrue[0m
    [22m[35mgap> r:=RandomRatExp(2);[0m
    [22m[35maUb[0m
    [22m[35mgap> IsEmptyLang(r);[0m
    [22m[35mfalse[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.3-2 IsFullLang[0m
  
  [1m[34m> IsFullLang( [0m[22m[34mR[0m[1m[34m ) __________________________________________________[0mfunction
  
  This  function  tests if the language given through a rational expression or
  an automaton [22m[34m R [0m represents the Kleene closure of the alphabet of [22m[34m R [0m .
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RationalExpression("aUb");[0m
    [22m[35maUb[0m
    [22m[35mgap> IsFullLang(r);[0m
    [22m[35mfalse[0m
    [22m[35mgap> r:=RationalExpression("(aUb)*");[0m
    [22m[35m(aUb)*[0m
    [22m[35mgap> IsFullLang(r);[0m
    [22m[35mtrue[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.3-3 AreEqualLang[0m
  
  [1m[34m> AreEqualLang( [0m[22m[34mA1, A2[0m[1m[34m ) ___________________________________________[0mfunction
  [1m[34m> AreEquivAut( [0m[22m[34mA1, A2[0m[1m[34m ) ____________________________________________[0mfunction
  
  These  functions,  which  are  synonyms,  test  if  the automata or rational
  expressions [22m[34mA1[0m and [22m[34mA2[0m are equivalent, i.e. represent the same language. This
  is  performed  by  checking  that  the  corresponding  minimal  automata are
  isomorphic.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> y:=RandomAutomaton("det",4,2);;[0m
    [22m[35mgap> x:=RandomAutomaton("det",4,2);;[0m
    [22m[35mgap> AreEquivAut(x, y);[0m
    [22m[35mfalse[0m
    [22m[35mgap> a:=RationalExpression("(aUb)*ab*");[0m
    [22m[35m(aUb)*ab*[0m
    [22m[35mgap> b:=RationalExpression("(aUb)*");[0m
    [22m[35m(aUb)*[0m
    [22m[35mgap> AreEqualLang(a, b);[0m
    [22m[35mfalse[0m
    [22m[35mgap> a:=RationalExpression("(bUa)*");[0m
    [22m[35m(bUa)*[0m
    [22m[35mgap> AreEqualLang(a, b);[0m
    [22m[35mtrue[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.3-4 IsContainedLang[0m
  
  [1m[34m> IsContainedLang( [0m[22m[34mR1, R2[0m[1m[34m ) ________________________________________[0mfunction
  
  Tests  if  the  language  represented  (through  an  automaton or a rational
  expression)  by  [22m[34m  R1  [0m is contained in the language represented (through an
  automaton or a rational expression) by [22m[34m R2 [0m .
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RationalExpression("aUab");[0m
    [22m[35maUab[0m
    [22m[35mgap> s:=RationalExpression("a","ab");[0m
    [22m[35ma[0m
    [22m[35mgap> IsContainedLang(s,r);[0m
    [22m[35mtrue[0m
    [22m[35mgap> IsContainedLang(r,s);[0m
    [22m[35mfalse[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.3-5 AreDisjointLang[0m
  
  [1m[34m> AreDisjointLang( [0m[22m[34mR1, R2[0m[1m[34m ) ________________________________________[0mfunction
  
  Tests   if  the  languages  represented  (through  automata  or  a  rational
  expressions) by [22m[34m R1 [0m and [22m[34m R2 [0m are disjoint.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RationalExpression("aUab");;[0m
    [22m[35mgap> s:=RationalExpression("a","ab");;[0m
    [22m[35mgap> AreDisjointLang(r,s);[0m
    [22m[35mfalse[0m
  [22m[35m------------------------------------------------------------------[0m
  
