  
  [1m[4m[31m3. Rational languages[0m
  
  Rational   languages   are   conveniently   represented   through   rational
  expressions. These are finite expressions involving letters of the alphabet;
  [22m[32mconcatenation[0m,  corresponding to the [22m[36mproduct[0m; the symbol [22m[32mU[0m, corresponding to
  the [22m[36munion[0m; and the symbol [22m[32m*[0m, corresponding to the Kleene's star.
  
  
  [1m[4m[31m3.1 Rational Expressions[0m
  
  The  expressions [22m[32m@[0m and [22m[32m"empty\_set"[0m are used to represent the empty word and
  the empty set respectively.
  
  [1m[4m[31m3.1-1 RationalExpression[0m
  
  [1m[34m> RationalExpression( [0m[22m[34mexpr[, alph][0m[1m[34m ) _______________________________[0mfunction
  
  A  rational expression can be created using the function [22m[32mRationalExpression[0m.
  [22m[34mexpr[0m is a string representing the desired expression literally and [22m[34malph[0m (may
  or  may  not  be  present) is the alphabet of the expression. Of course [22m[34malph[0m
  must  not  contain  the symbols '@', '(', ')', '*' nor 'U'. When [22m[34malph[0m 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.)
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> RationalExpression("abUc");[0m
    [22m[35mabUc[0m
    [22m[35mgap> RationalExpression("ab*Uc");[0m
    [22m[35mab*Uc[0m
    [22m[35mgap> RationalExpression("001U1*");[0m
    [22m[35m001U1*[0m
    [22m[35mgap> RationalExpression("001U1*","012");[0m
    [22m[35m001U1*[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-2 RatExpOnnLetters[0m
  
  [1m[34m> RatExpOnnLetters( [0m[22m[34mn, operation, list[0m[1m[34m ) ___________________________[0mfunction
  
  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). [22m[34moperation[0m is the name of an
  operation,  the  possibilities being: [22m[32mproduct[0m, [22m[32munion[0m or [22m[32mstar[0m. [22m[34mlist[0m 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 [22m[32m[ ][0m and [22m[32mempty\_set[0m are other possibilities for [22m[32mlist[0m.
  An example follows
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> RatExpOnnLetters(2,"star",RatExpOnnLetters(2,"product",[0m
    [22m[35m> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,"union",[0m
    [22m[35m> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,[],[2])])]));      [0m
    [22m[35m(a(aUb))*[0m
  [22m[35m------------------------------------------------------------------[0m
  
  The empty word and the empty set are the rational expressions:
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> RatExpOnnLetters(2,[],[]);         [0m
    [22m[35m@[0m
    [22m[35mgap> RatExpOnnLetters(2,[],"empty_set");[0m
    [22m[35mempty_set[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-3 RandomRatExp[0m
  
  [1m[34m> RandomRatExp( [0m[22m[34marg[0m[1m[34m ) ______________________________________________[0mfunction
  
  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.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> RandomRatExp(2);[0m
    [22m[35mb*(@Ua)[0m
    [22m[35mgap> RandomRatExp("01");[0m
    [22m[35mempty_set[0m
    [22m[35mgap> RandomRatExp("01");[0m
    [22m[35m(0U1)*[0m
    [22m[35mgap> RandomRatExp("01",7);[0m
    [22m[35m0*1(@U0U1)[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-4 SizeRatExp[0m
  
  [1m[34m> SizeRatExp( [0m[22m[34mr[0m[1m[34m ) __________________________________________________[0mfunction
  
  Returns  the  size,  i.e.  the  number  of  symbols  of the alphabet, of the
  rational expression [22m[34mr[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> a:=RationalExpression("0*1(@U0U1)");[0m
    [22m[35m0*1(@U0U1)[0m
    [22m[35mgap> SizeRatExp(a);[0m
    [22m[35m4[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-5 IsRationalExpression[0m
  
  [1m[34m> IsRationalExpression( [0m[22m[34mr[0m[1m[34m ) ________________________________________[0mfunction
  
  Tests whether an object is a rational expression.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> IsRatExpOnnLettersObj(r3) and IsRationalExpressionRep(r3);[0m
    [22m[35mtrue[0m
    [22m[35mgap> IsRationalExpression(r1);[0m
    [22m[35mtrue[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-6 AlphabetOfRatExp[0m
  
  [1m[34m> AlphabetOfRatExp( [0m[22m[34mR[0m[1m[34m ) ____________________________________________[0mfunction
  
  Returns the alphabet of the rational expression [22m[32mR[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RandomRatExp(2);[0m
    [22m[35ma*(ba*U@)[0m
    [22m[35mgap> AlphabetOfRatExp(r);[0m
    [22m[35m2[0m
    [22m[35mgap> r:=RandomRatExp("01");[0m
    [22m[35m1*(01*U@)[0m
    [22m[35mgap> AlphabetOfRatExp(r);[0m
    [22m[35m"01"[0m
    [22m[35mgap> a:=RandomTransformation(3);;[0m
    [22m[35mgap> b:=RandomTransformation(3);;[0m
    [22m[35mgap> r:=RandomRatExp([a,b]);[0m
    [22m[35m(Transformation( [ 1, 1, 3 ] )UTransformation( [ 1, 1, 2 ] ))*[0m
    [22m[35mgap> AlphabetOfRatExp(r);[0m
    [22m[35m[ Transformation( [ 1, 1, 3 ] ), Transformation( [ 1, 1, 2 ] ) ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-7 AlphabetOfRatExpAsList[0m
  
  [1m[34m> AlphabetOfRatExpAsList( [0m[22m[34mR[0m[1m[34m ) ______________________________________[0mfunction
  
  Returns  the  alphabet of the rational expression [22m[32mR[0m always as a list. If the
  alphabet  of  the  rational expression is an integer less than 27 it returns
  the list [22m[32m"abcd...."[0m, otherwise returns [22m[32m[ "a1", "a2", "a3", "a4", ... ][0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RandomRatExp(2);[0m
    [22m[35m(aUb)((aUb)(bU@)U@)U@[0m
    [22m[35mgap> AlphabetOfRatExpAsList(r);[0m
    [22m[35m"ab"[0m
    [22m[35mgap> r:=RandomRatExp("01");[0m
    [22m[35m1*(0U@)[0m
    [22m[35mgap> AlphabetOfRatExpAsList(r);[0m
    [22m[35m"01"[0m
    [22m[35mgap> r:=RandomRatExp(30);;[0m
    [22m[35mgap> AlphabetOfRatExpAsList(r);[0m
    [22m[35m[ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", [0m
    [22m[35m"a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21", [0m
    [22m[35m"a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m3.1-8 CopyRatExp[0m
  
  [1m[34m> CopyRatExp( [0m[22m[34mR[0m[1m[34m ) __________________________________________________[0mfunction
  
  Returns a new rational expression, which is a copy of [22m[32mR[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r:=RandomRatExp(2);[0m
    [22m[35ma*(bU@)[0m
    [22m[35mgap> CopyRatExp(r);[0m
    [22m[35ma*(bU@)[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m3.2 Comparison of rational expressions[0m
  
  The way two rational expressions [22m[32mr1[0m and [22m[32mr2[0m 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;
  
  
  [1m[4m[31m3.3 Operations with rational languages[0m
  
  Only operations with rational languages over the same alphabet are allowed.
  
  We  may compute expressions for the [22m[32mproduct[0m, [22m[32munion[0m and [22m[32mstar[0m (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  [22m[32mUnionRatExp[0m,  [22m[32mProductRatExp[0m, [22m[32mStarRatExp[0m, that return respectively
  rational expressions for the [22m[36munion[0m and [22m[36mproduct[0m of the languages given by the
  rational  expressions  [22m[32mr[0m  and  [22m[32ms[0m  and  the [22m[32mstar[0m of the language given by the
  rational expression [22m[32mr[0m.
  
  [1m[4m[31m3.3-1 UnionRatExp[0m
  
  [1m[34m> UnionRatExp( [0m[22m[34mr, s[0m[1m[34m ) ______________________________________________[0mfunction
  [1m[4m[31m3.3-2 ProductRatExp[0m
  
  [1m[34m> ProductRatExp( [0m[22m[34mr, s[0m[1m[34m ) ____________________________________________[0mfunction
  [1m[4m[31m3.3-3  StarRatExp[0m
  
  [1m[34m>  StarRatExp( [0m[22m[34mr[0m[1m[34m ) _________________________________________________[0mfunction
  
  The expression [22m[32m(a(aUb))*[0m may be produced in the following way
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> r1 := RatExpOnnLetters(2,[],[1]); [0m
    [22m[35ma[0m
    [22m[35mgap> r2 := RatExpOnnLetters(2,[],[2]);[0m
    [22m[35mb[0m
    [22m[35mgap> r3 := UnionRatExp(r1,r2);[0m
    [22m[35maUb[0m
    [22m[35mgap> r4 := ProductRatExp(r1,r3);[0m
    [22m[35ma(aUb)[0m
    [22m[35mgap> r5 := StarRatExp(r4);[0m
    [22m[35m(a(aUb))*[0m
  [22m[35m------------------------------------------------------------------[0m
  
