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.
The expressions @ and "empty\_set" are used to represent the empty word and the empty set respectively.
‣ 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.)
gap> RationalExpression("abUc"); abUc gap> RationalExpression("ab*Uc"); ab*Uc gap> RationalExpression("001U1*"); 001U1* gap> RationalExpression("001U1*","012"); 001U1*
‣ 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,\ldots\}\) 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
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:
gap> RatExpOnnLetters(2,[],[]); @ gap> RatExpOnnLetters(2,[],"empty_set"); empty_set
‣ 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.
gap> RandomRatExp(2); b*(@Ua) gap> RandomRatExp("01"); empty_set gap> RandomRatExp("01"); (0U1)* gap> RandomRatExp("01",7); 0*1(@U0U1)
‣ SizeRatExp( r ) | ( function ) |
Returns the size, i.e. the number of symbols of the alphabet, of the rational expression r.
gap> a:=RationalExpression("0*1(@U0U1)"); 0*1(@U0U1) gap> SizeRatExp(a); 5
‣ IsRationalExpression( r ) | ( function ) |
Tests whether an object is a rational expression.
gap> r := RationalExpression("1(0U1)U@"); 1(0U1)U@ gap> IsRatExpOnnLettersObj(r) and IsRationalExpressionRep(r); true gap> IsRationalExpression(RandomRatExp("01")); true
‣ AlphabetOfRatExp( R ) | ( function ) |
Returns the number of symbols in the alphabet of the rational expression R.
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
‣ 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", ... ].
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" ]
‣ CopyRatExp( R ) | ( function ) |
Returns a new rational expression, which is a copy of R.
gap> r:=RandomRatExp(2); a*(bU@) gap> CopyRatExp(r); a*(bU@)
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;
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, rU"empty_set" = r and r@ = r . 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.
‣ UnionRatExp( r, s ) | ( function ) |
‣ ProductRatExp( r, s ) | ( function ) |
‣ StarRatExp( r ) | ( function ) |
The expression (a(aUb))* may be produced in the following way
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))*
generated by GAPDoc2HTML