[1X3 Rational languages[0X Rational languages are conveniently represented through rational expressions. These are finite expressions involving letters of the alphabet; [10Xconcatenation[0m, corresponding to the [13Xproduct[0m; the symbol [10XU[0m, corresponding to the [13Xunion[0m; and the symbol [10X*[0m, corresponding to the Kleene's star. [1X3.1 Rational Expressions[0X The expressions [10X@[0m and [10X"empty\_set"[0m are used to represent the empty word and the empty set respectively. [1X3.1-1 RationalExpression[0m [2X> RationalExpression( [0X[3Xexpr[, alph][0X[2X ) _______________________________[0Xfunction A rational expression can be created using the function [10XRationalExpression[0m. [3Xexpr[0m is a string representing the desired expression literally and [3Xalph[0m (may or may not be present) is the alphabet of the expression. Of course [3Xalph[0m must not contain the symbols '@', '(', ')', '*' nor 'U'. When [3Xalph[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.) [4X--------------------------- Example ----------------------------[0X [4Xgap> RationalExpression("abUc");[0X [4XabUc[0X [4Xgap> RationalExpression("ab*Uc");[0X [4Xab*Uc[0X [4Xgap> RationalExpression("001U1*");[0X [4X001U1*[0X [4Xgap> RationalExpression("001U1*","012");[0X [4X001U1*[0X [4X------------------------------------------------------------------[0X [1X3.1-2 RatExpOnnLetters[0m [2X> RatExpOnnLetters( [0X[3Xn, operation, list[0X[2X ) ___________________________[0Xfunction 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). [3Xoperation[0m is the name of an operation, the possibilities being: [10Xproduct[0m, [10Xunion[0m or [10Xstar[0m. [3Xlist[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 [10X[ ][0m and [10Xempty\_set[0m are other possibilities for [10Xlist[0m. An example follows [4X--------------------------- Example ----------------------------[0X [4Xgap> RatExpOnnLetters(2,"star",RatExpOnnLetters(2,"product",[0X [4X> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,"union",[0X [4X> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,[],[2])])])); [0X [4X(a(aUb))*[0X [4X------------------------------------------------------------------[0X The empty word and the empty set are the rational expressions: [4X--------------------------- Example ----------------------------[0X [4Xgap> RatExpOnnLetters(2,[],[]); [0X [4X@[0X [4Xgap> RatExpOnnLetters(2,[],"empty_set");[0X [4Xempty_set[0X [4X------------------------------------------------------------------[0X [1X3.1-3 RandomRatExp[0m [2X> RandomRatExp( [0X[3Xarg[0X[2X ) ______________________________________________[0Xfunction 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. [4X--------------------------- Example ----------------------------[0X [4Xgap> RandomRatExp(2);[0X [4Xb*(@Ua)[0X [4Xgap> RandomRatExp("01");[0X [4Xempty_set[0X [4Xgap> RandomRatExp("01");[0X [4X(0U1)*[0X [4Xgap> RandomRatExp("01",7);[0X [4X0*1(@U0U1)[0X [4X------------------------------------------------------------------[0X [1X3.1-4 SizeRatExp[0m [2X> SizeRatExp( [0X[3Xr[0X[2X ) __________________________________________________[0Xfunction Returns the size, i.e. the number of symbols of the alphabet, of the rational expression [3Xr[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RationalExpression("0*1(@U0U1)");[0X [4X0*1(@U0U1)[0X [4Xgap> SizeRatExp(a);[0X [4X5[0X [4X------------------------------------------------------------------[0X [1X3.1-5 IsRationalExpression[0m [2X> IsRationalExpression( [0X[3Xr[0X[2X ) ________________________________________[0Xfunction Tests whether an object is a rational expression. [4X--------------------------- Example ----------------------------[0X [4Xgap> IsRatExpOnnLettersObj(r3) and IsRationalExpressionRep(r3);[0X [4Xtrue[0X [4Xgap> IsRationalExpression(r1);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X3.1-6 AlphabetOfRatExp[0m [2X> AlphabetOfRatExp( [0X[3XR[0X[2X ) ____________________________________________[0Xfunction Returns the number of symbols in the alphabet of the rational expression [10XR[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RandomRatExp(2);[0X [4Xa*(ba*U@)[0X [4Xgap> AlphabetOfRatExp(r);[0X [4X2[0X [4Xgap> r:=RandomRatExp("01");[0X [4X1*(01*U@)[0X [4Xgap> AlphabetOfRatExp(r);[0X [4X2[0X [4Xgap> a:=RandomTransformation(3);;[0X [4Xgap> b:=RandomTransformation(3);;[0X [4Xgap> r:=RandomRatExp([a,b]);[0X [4X(Transformation( [ 1, 1, 3 ] )UTransformation( [ 1, 1, 2 ] ))*[0X [4Xgap> AlphabetOfRatExp(r);[0X [4X[ Transformation( [ 1, 1, 3 ] ), Transformation( [ 1, 1, 2 ] ) ][0X [4X------------------------------------------------------------------[0X [1X3.1-7 AlphabetOfRatExpAsList[0m [2X> AlphabetOfRatExpAsList( [0X[3XR[0X[2X ) ______________________________________[0Xfunction Returns the alphabet of the rational expression [10XR[0m 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 [10X"abcd...."[0m, otherwise returns [10X[ "a1", "a2", "a3", "a4", ... ][0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RandomRatExp(2);[0X [4X(aUb)((aUb)(bU@)U@)U@[0X [4Xgap> AlphabetOfRatExpAsList(r);[0X [4X"ab"[0X [4Xgap> r:=RandomRatExp("01");[0X [4X1*(0U@)[0X [4Xgap> AlphabetOfRatExpAsList(r);[0X [4X"01"[0X [4Xgap> r:=RandomRatExp(30);;[0X [4Xgap> AlphabetOfRatExpAsList(r);[0X [4X[ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", [0X [4X"a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21", [0X [4X"a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ][0X [4X------------------------------------------------------------------[0X [1X3.1-8 CopyRatExp[0m [2X> CopyRatExp( [0X[3XR[0X[2X ) __________________________________________________[0Xfunction Returns a new rational expression, which is a copy of [10XR[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RandomRatExp(2);[0X [4Xa*(bU@)[0X [4Xgap> CopyRatExp(r);[0X [4Xa*(bU@)[0X [4X------------------------------------------------------------------[0X [1X3.2 Comparison of rational expressions[0X The way two rational expressions [10Xr1[0m and [10Xr2[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; [1X3.3 Operations with rational languages[0X Only operations with rational languages over the same alphabet are allowed. We may compute expressions for the [10Xproduct[0m, [10Xunion[0m and [10Xstar[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 [10XUnionRatExp[0m, [10XProductRatExp[0m, [10XStarRatExp[0m, that return respectively rational expressions for the [13Xunion[0m and [13Xproduct[0m of the languages given by the rational expressions [10Xr[0m and [10Xs[0m and the [10Xstar[0m of the language given by the rational expression [10Xr[0m. [1X3.3-1 UnionRatExp[0m [2X> UnionRatExp( [0X[3Xr, s[0X[2X ) ______________________________________________[0Xfunction [1X3.3-2 ProductRatExp[0m [2X> ProductRatExp( [0X[3Xr, s[0X[2X ) ____________________________________________[0Xfunction [1X3.3-3 StarRatExp[0m [2X> StarRatExp( [0X[3Xr[0X[2X ) _________________________________________________[0Xfunction The expression [10X(a(aUb))*[0m may be produced in the following way [4X--------------------------- Example ----------------------------[0X [4Xgap> r1 := RatExpOnnLetters(2,[],[1]); [0X [4Xa[0X [4Xgap> r2 := RatExpOnnLetters(2,[],[2]);[0X [4Xb[0X [4Xgap> r3 := UnionRatExp(r1,r2);[0X [4XaUb[0X [4Xgap> r4 := ProductRatExp(r1,r3);[0X [4Xa(aUb)[0X [4Xgap> r5 := StarRatExp(r4);[0X [4X(a(aUb))*[0X [4X------------------------------------------------------------------[0X