chap4.txt

  
  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
  
  
  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