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,...} 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 := RandomRatExp("01",7); 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