Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | A | B | Bib | C | Ind

### 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.)

    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

    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

##### 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.

    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.

    gap> a:=RationalExpression("0*1(@U0U1)");
    0*1(@U0U1)
    gap> SizeRatExp(a);
    4

##### 3.1-5 IsRationalExpression

`> IsRationalExpression`( r ) | ( function )

Tests whether an object is a rational expression.

    gap> IsRatExpOnnLettersObj(r3) and IsRationalExpressionRep(r3);
    true
    gap> IsRationalExpression(r1);
    true

#### 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, 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`.

##### 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

    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))*

Top of Book | Previous Chapter | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | A | B | Bib | C | Ind

generated by GAPDoc2HTML