<!-- $Id: rational.xml,v 1.12 Exp $ --> <Chapter><Heading>Rational languages</Heading> Rational languages are conveniently represented through rational expressions. These are finite expressions involving letters of the alphabet; <C>concatenation</C>, corresponding to the <E>product</E>; the symbol <C>U</C>, corresponding to the <E>union</E>; and the symbol <C>*</C>, corresponding to the Kleene's star. <Index>rational expressions</Index> <Section><Heading>Rational Expressions</Heading> The expressions <C>@</C> and <C>"empty\_set"</C> are used to represent the empty word and the empty set respectively. <ManSection> <Func Name="RationalExpression" Arg=" expr[, alph] "/> <Description> A rational expression can be created using the function <C>RationalExpression</C>. <A>expr</A> is a string representing the desired expression literally and <A>alph</A> (may or may not be present) is the alphabet of the expression. Of course <A>alph</A> must not contain the symbols '@', '(', ')', '*' nor 'U'. When <A>alph</A> 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.) <Example><![CDATA[ gap> RationalExpression("abUc"); abUc gap> RationalExpression("ab*Uc"); ab*Uc gap> RationalExpression("001U1*"); 001U1* gap> RationalExpression("001U1*","012"); 001U1* ]]></Example> </Description> </ManSection> <ManSection> <Func Name="RatExpOnnLetters" Arg=" n, operation, list "/> <Description> This is another way to construct a rational expression over an alphabet. The user may specify the alphabet or just give the number <M>n</M> of letters (in this case the alphabet <M>\{a,b,c,\ldots\}</M> is considered). <A>operation</A> is the name of an operation, the possibilities being: <C>product</C>, <C>union</C> or <C>star</C>. <A>list</A> 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 <C>[ ]</C> and <C>empty\_set</C> are other possibilities for <C>list</C>. An example follows <Example><![CDATA[ gap> RatExpOnnLetters(2,"star",RatExpOnnLetters(2,"product", > [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,"union", > [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,[],[2])])])); (a(aUb))* ]]></Example> The empty word and the empty set are the rational expressions: <Example><![CDATA[ gap> RatExpOnnLetters(2,[],[]); @ gap> RatExpOnnLetters(2,[],"empty_set"); empty_set ]]></Example> </Description></ManSection> <ManSection> <Func Name="RandomRatExp" Arg="arg"/> <Description> Given the number of symbols of the alphabet and (possibly) a factor <M>m</M> which is intended to increase the randomality of the expression, returns a pseudo random rational expression over that alphabet. <Example><![CDATA[ gap> RandomRatExp(2); b*(@Ua) gap> RandomRatExp("01"); empty_set gap> RandomRatExp("01"); (0U1)* gap> RandomRatExp("01",7); 0*1(@U0U1) ]]></Example> </Description> </ManSection> <ManSection> <Func Name="SizeRatExp" Arg="r"/> <Description> Returns the size, i.e. the number of symbols of the alphabet, of the rational expression <A>r</A>. <Example><![CDATA[ gap> a:=RationalExpression("0*1(@U0U1)"); 0*1(@U0U1) gap> SizeRatExp(a); 5 ]]></Example> </Description> </ManSection> <ManSection> <Func Name="IsRationalExpression" Arg="r"/> <Description> Tests whether an object is a rational expression. <Example><![CDATA[ gap> IsRatExpOnnLettersObj(r3) and IsRationalExpressionRep(r3); true gap> IsRationalExpression(r1); true ]]></Example> </Description> </ManSection> <ManSection> <Func Name="AlphabetOfRatExp" Arg="R"/> <Description> Returns the number of symbols in the alphabet of the rational expression <C>R</C>. <Example><![CDATA[ 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); [ Transformation( [ 1, 1, 3 ] ), Transformation( [ 1, 1, 2 ] ) ] ]]></Example> </Description> </ManSection> <ManSection> <Func Name="AlphabetOfRatExpAsList" Arg="R"/> <Description> Returns the alphabet of the rational expression <C>R</C> 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 <C>"abcd...."</C>, otherwise returns <C>[ "a1", "a2", "a3", "a4", ... ]</C>. <Example><![CDATA[ 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" ] ]]></Example> </Description> </ManSection> <ManSection> <Func Name="CopyRatExp" Arg="R"/> <Description> Returns a new rational expression, which is a copy of <C>R</C>. <Example><![CDATA[ gap> r:=RandomRatExp(2); a*(bU@) gap> CopyRatExp(r); a*(bU@) ]]></Example> </Description> </ManSection> </Section> <Section><Heading>Comparison of rational expressions</Heading> The way two rational expressions <C>r1</C> and <C>r2</C> are compared through the <Alt Only="LaTeX"> $<![CDATA[<]]>$ </Alt> <Alt Only="HTML"> < </Alt> 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; </Section> <Section><Heading>Operations with rational languages</Heading> Only operations with rational languages over the same alphabet are allowed. <P/> We may compute expressions for the <C>product</C>, <C>union</C> and <C>star</C> (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, <Alt Only="LaTeX"> $r\cup"empty_set" = r$ </Alt> <Alt Only="HTML"> rU"empty_set" = r </Alt> and <Alt Only="LaTeX"> $r\epsilon = r$ </Alt> <Alt Only="HTML"> r@ = r </Alt>. Of course, these operations may be used to construct more complex expressions. For rational expressions we have the functions <C>UnionRatExp</C>, <C>ProductRatExp</C>, <C>StarRatExp</C>, that return respectively rational expressions for the <E>union</E> and <E>product</E> of the languages given by the rational expressions <C>r</C> and <C>s</C> and the <C>star</C> of the language given by the rational expression <C>r</C>. <ManSection> <Func Name="UnionRatExp" Arg="r,s"/> </ManSection> <ManSection> <Func Name="ProductRatExp" Arg="r,s"/> </ManSection> <ManSection> <Func Name=" StarRatExp" Arg="r"/> <Description> The expression <C>(a(aUb))*</C> may be produced in the following way <Example><![CDATA[ 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))* ]]></Example> </Description></ManSection> </Section> </Chapter>