chap3.txt

  
  3 Rational languages
  
  Rational   languages   are   conveniently   represented   through   rational
  expressions. These are finite expressions involving letters of the alphabet;
  concatenation,  corresponding to the product; the symbol U, corresponding to
  the union; and the symbol *, corresponding to the Kleene's star.
  
  
  3.1 Rational Expressions
  
  The  expressions @ and "empty\_set" are used to represent the empty word and
  the empty set respectively.
  
  3.1-1 RationalExpression
  
  RationalExpression( expr[, alph] )  function
  
  A  rational expression can be created using the function RationalExpression.
  expr is a string representing the desired expression literally and alph (may
  or  may  not  be  present) is the alphabet of the expression. Of course alph
  must  not  contain  the symbols '@', '(', ')', '*' nor 'U'. When alph is not
  present,  the  alphabet  of  the  rational  expression is the set of symbols
  (other  than '"', etc...) occurring in the expression. (The alphabet is then
  ordered with the alphabetical order.)
  
    Example  
    gap> RationalExpression("abUc");
    abUc
    gap> RationalExpression("ab*Uc");
    ab*Uc
    gap> RationalExpression("001U1*");
    001U1*
    gap> RationalExpression("001U1*","012");
    001U1*
  
  
  3.1-2 RatExpOnnLetters
  
  RatExpOnnLetters( n, operation, list )  function
  
  This is another way to construct a rational expression over an alphabet. The
  user  may specify the alphabet or just give the number n of letters (in this
  case  the  alphabet  {a,b,c,...} is considered). operation is the name of an
  operation,  the  possibilities being: product, union or star. list is a list
  of rational expressions, a rational expression in the case of ``star'', or a
  list  consisting  of  an  integer  when  the rational expression is a single
  letter.  The empty list [ ] and empty\_set are other possibilities for list.
  An example follows
  
    Example  
    gap> RatExpOnnLetters(2,"star",RatExpOnnLetters(2,"product",
    > [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,"union",
    > [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,[],[2])])]));      
    (a(aUb))*
  
  
  The empty word and the empty set are the rational expressions:
  
    Example  
    gap> RatExpOnnLetters(2,[],[]);         
    @
    gap> RatExpOnnLetters(2,[],"empty_set");
    empty_set
  
  
  3.1-3 RandomRatExp
  
  RandomRatExp( arg )  function
  
  Given  the number of symbols of the alphabet and (possibly) a factor m which
  is  intended to increase the randomality of the expression, returns a pseudo
  random rational expression over that alphabet.
  
    Example  
    gap> RandomRatExp(2);
    b*(@Ua)
    gap> RandomRatExp("01");
    empty_set
    gap> RandomRatExp("01");
    (0U1)*
    gap> RandomRatExp("01",7);
    0*1(@U0U1)
  
  
  3.1-4 SizeRatExp
  
  SizeRatExp( r )  function
  
  Returns  the  size,  i.e.  the  number  of  symbols  of the alphabet, of the
  rational expression r.
  
    Example  
    gap> a:=RationalExpression("0*1(@U0U1)");
    0*1(@U0U1)
    gap> SizeRatExp(a);
    5
  
  
  3.1-5 IsRationalExpression
  
  IsRationalExpression( r )  function
  
  Tests whether an object is a rational expression.
  
    Example  
    gap> r := RandomRatExp("01",7);
    1(0U1)U@
    gap> IsRatExpOnnLettersObj(r) and IsRationalExpressionRep(r);
    true
    gap> IsRationalExpression(RandomRatExp("01"));
    true
  
  
  3.1-6 AlphabetOfRatExp
  
  AlphabetOfRatExp( R )  function
  
  Returns the number of symbols in the alphabet of the rational expression R.
  
    Example  
    gap> r:=RandomRatExp(2);
    a*(ba*U@)
    gap> AlphabetOfRatExp(r);
    2
    gap> r:=RandomRatExp("01");
    1*(01*U@)
    gap> AlphabetOfRatExp(r);
    2
    gap> a:=RandomTransformation(3);;
    gap> b:=RandomTransformation(3);;
    gap> r:=RandomRatExp([a,b]);
    (Transformation( [ 1, 1, 3 ] )UTransformation( [ 1, 1, 2 ] ))*
    gap> AlphabetOfRatExp(r);
    2
  
  
  3.1-7 AlphabetOfRatExpAsList
  
  AlphabetOfRatExpAsList( R )  function
  
  Returns  the  alphabet of the rational expression R always as a list. If the
  alphabet  of  the  rational  expression is given by means of an integer less
  than  27  it  returns  the  list "abcd....", otherwise returns [ "a1", "a2",
  "a3", "a4", ... ].
  
    Example  
    gap> r:=RandomRatExp(2);
    (aUb)((aUb)(bU@)U@)U@
    gap> AlphabetOfRatExpAsList(r);
    "ab"
    gap> r:=RandomRatExp("01");
    1*(0U@)
    gap> AlphabetOfRatExpAsList(r);
    "01"
    gap> r:=RandomRatExp(30);;
    gap> AlphabetOfRatExpAsList(r);
    [ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", 
    "a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21", 
    "a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ]
  
  
  3.1-8 CopyRatExp
  
  CopyRatExp( R )  function
  
  Returns a new rational expression, which is a copy of R.
  
    Example  
    gap> r:=RandomRatExp(2);
    a*(bU@)
    gap> CopyRatExp(r);
    a*(bU@)
  
  
  
  3.2 Comparison of rational expressions
  
  The way two rational expressions r1 and r2 are compared through the operator
  is the following: the empty set is lesser than everything else; if r1 and r2
  are  letters, then the lesser is taken from the order in the alphabet; if r1
  is  a  letter  an  r2 a product, union or star, then r1 is lesser than r2; a
  star  expression  is  considered  to  be  lesser  than  a  product  or union
  expression  and  a  product  lesser  than  a  union;  to  compare  two  star
  expressions  we  compare  the  expressions  under  the stars; to compare two
  product   or  union  expressions  we  compare  the  subexpressions  of  each
  expression from left to right;
  
  
  3.3 Operations with rational languages
  
  Only operations with rational languages over the same alphabet are allowed.
  
  We  may compute expressions for the product, union and star (i.e., submonoid
  generated   by)  of  rational  sets.  In  some  cases,  simpler  expressions
  representing  the  same set are returned. Note that that two simplifications
  are  always  made,  namely, and . Of course, these operations may be used to
  construct  more  complex  expressions.  For rational expressions we have the
  functions  UnionRatExp,  ProductRatExp, StarRatExp, that return respectively
  rational expressions for the union and product of the languages given by the
  rational  expressions  r  and  s  and  the star of the language given by the
  rational expression r.
  
  3.3-1 UnionRatExp
  
  UnionRatExp( r, s )  function
  3.3-2 ProductRatExp
  
  ProductRatExp( r, s )  function
  3.3-3  StarRatExp
  
   StarRatExp( r )  function
  
  The expression (a(aUb))* may be produced in the following way
  
    Example  
    gap> r1 := RatExpOnnLetters(2,[],[1]); 
    a
    gap> r2 := RatExpOnnLetters(2,[],[2]);
    b
    gap> r3 := UnionRatExp(r1,r2);
    aUb
    gap> r4 := ProductRatExp(r1,r3);
    a(aUb)
    gap> r5 := StarRatExp(r4);
    (a(aUb))*