<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Automata) - Chapter 3: Rational languages</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapC.html">C</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<p><a id="X833D315483172905" name="X833D315483172905"></a></p>
<div class="ChapSects"><a href="chap3.html#X833D315483172905">3 <span class="Heading">Rational languages</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7C144D368043DE01">3.1 <span class="Heading">Rational Expressions</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X801EC6F38568426D">3.1-1 RationalExpression</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7EE5A70F7F237C41">3.1-2 RatExpOnnLetters</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7DA59CBE8571796C">3.1-3 RandomRatExp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E3AA84784019E6C">3.1-4 SizeRatExp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7DDB46817D6E79BE">3.1-5 IsRationalExpression</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8773359880149A98">3.1-6 AlphabetOfRatExp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X84B9922B7C006158">3.1-7 AlphabetOfRatExpAsList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X786A096681CAC3CD">3.1-8 CopyRatExp</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7FB9270D7E8FABF3">3.2 <span class="Heading">Comparison of rational expressions</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X83A280D47DB3A033">3.3 <span class="Heading">Operations with rational languages</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8206BD4E82A81D8F">3.3-1 UnionRatExp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E29107587611CE2">3.3-2 ProductRatExp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X83D8DAE6862C8A96">3.3-3 StarRatExp</a></span>
</div>
</div>
<h3>3 <span class="Heading">Rational languages</span></h3>
<p>Rational languages are conveniently represented through rational expressions. These are finite expressions involving letters of the alphabet; <code class="code">concatenation</code>, corresponding to the <em>product</em>; the symbol <code class="code">U</code>, corresponding to the <em>union</em>; and the symbol <code class="code">*</code>, corresponding to the Kleene's star.</p>
<p><a id="X7C144D368043DE01" name="X7C144D368043DE01"></a></p>
<h4>3.1 <span class="Heading">Rational Expressions</span></h4>
<p>The expressions <code class="code">@</code> and <code class="code">"empty\_set"</code> are used to represent the empty word and the empty set respectively.</p>
<p><a id="X801EC6F38568426D" name="X801EC6F38568426D"></a></p>
<h5>3.1-1 RationalExpression</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RationalExpression</code>( <var class="Arg">expr[, alph]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A rational expression can be created using the function <code class="code">RationalExpression</code>. <var class="Arg">expr</var> is a string representing the desired expression literally and <var class="Arg">alph</var> (may or may not be present) is the alphabet of the expression. Of course <var class="Arg">alph</var> must not contain the symbols '@', '(', ')', '*' nor 'U'. When <var class="Arg">alph</var> 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.)</p>
<table class="example">
<tr><td><pre>
gap> RationalExpression("abUc");
abUc
gap> RationalExpression("ab*Uc");
ab*Uc
gap> RationalExpression("001U1*");
001U1*
gap> RationalExpression("001U1*","012");
001U1*
</pre></td></tr></table>
<p><a id="X7EE5A70F7F237C41" name="X7EE5A70F7F237C41"></a></p>
<h5>3.1-2 RatExpOnnLetters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RatExpOnnLetters</code>( <var class="Arg">n, operation, list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>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). <var class="Arg">operation</var> is the name of an operation, the possibilities being: <code class="code">product</code>, <code class="code">union</code> or <code class="code">star</code>. <var class="Arg">list</var> 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 <code class="code">[ ]</code> and <code class="code">empty\_set</code> are other possibilities for <code class="code">list</code>. An example follows</p>
<table class="example">
<tr><td><pre>
gap> RatExpOnnLetters(2,"star",RatExpOnnLetters(2,"product",
> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,"union",
> [RatExpOnnLetters(2,[],[1]),RatExpOnnLetters(2,[],[2])])]));
(a(aUb))*
</pre></td></tr></table>
<p>The empty word and the empty set are the rational expressions:</p>
<table class="example">
<tr><td><pre>
gap> RatExpOnnLetters(2,[],[]);
@
gap> RatExpOnnLetters(2,[],"empty_set");
empty_set
</pre></td></tr></table>
<p><a id="X7DA59CBE8571796C" name="X7DA59CBE8571796C"></a></p>
<h5>3.1-3 RandomRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RandomRatExp</code>( <var class="Arg">arg</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>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.</p>
<table class="example">
<tr><td><pre>
gap> RandomRatExp(2);
b*(@Ua)
gap> RandomRatExp("01");
empty_set
gap> RandomRatExp("01");
(0U1)*
gap> RandomRatExp("01",7);
0*1(@U0U1)
</pre></td></tr></table>
<p><a id="X7E3AA84784019E6C" name="X7E3AA84784019E6C"></a></p>
<h5>3.1-4 SizeRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SizeRatExp</code>( <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the size, i.e. the number of symbols of the alphabet, of the rational expression <var class="Arg">r</var>.</p>
<table class="example">
<tr><td><pre>
gap> a:=RationalExpression("0*1(@U0U1)");
0*1(@U0U1)
gap> SizeRatExp(a);
5
</pre></td></tr></table>
<p><a id="X7DDB46817D6E79BE" name="X7DDB46817D6E79BE"></a></p>
<h5>3.1-5 IsRationalExpression</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsRationalExpression</code>( <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Tests whether an object is a rational expression.</p>
<table class="example">
<tr><td><pre>
gap> IsRatExpOnnLettersObj(r3) and IsRationalExpressionRep(r3);
true
gap> IsRationalExpression(r1);
true
</pre></td></tr></table>
<p><a id="X8773359880149A98" name="X8773359880149A98"></a></p>
<h5>3.1-6 AlphabetOfRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlphabetOfRatExp</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the number of symbols in the alphabet of the rational expression <code class="code">R</code>.</p>
<table class="example">
<tr><td><pre>
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 ] ) ]
</pre></td></tr></table>
<p><a id="X84B9922B7C006158" name="X84B9922B7C006158"></a></p>
<h5>3.1-7 AlphabetOfRatExpAsList</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlphabetOfRatExpAsList</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns the alphabet of the rational expression <code class="code">R</code> 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 <code class="code">"abcd...."</code>, otherwise returns <code class="code">[ "a1", "a2", "a3", "a4", ... ]</code>.</p>
<table class="example">
<tr><td><pre>
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" ]
</pre></td></tr></table>
<p><a id="X786A096681CAC3CD" name="X786A096681CAC3CD"></a></p>
<h5>3.1-8 CopyRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> CopyRatExp</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns a new rational expression, which is a copy of <code class="code">R</code>.</p>
<table class="example">
<tr><td><pre>
gap> r:=RandomRatExp(2);
a*(bU@)
gap> CopyRatExp(r);
a*(bU@)
</pre></td></tr></table>
<p><a id="X7FB9270D7E8FABF3" name="X7FB9270D7E8FABF3"></a></p>
<h4>3.2 <span class="Heading">Comparison of rational expressions</span></h4>
<p>The way two rational expressions <code class="code">r1</code> and <code class="code">r2</code> 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;</p>
<p><a id="X83A280D47DB3A033" name="X83A280D47DB3A033"></a></p>
<h4>3.3 <span class="Heading">Operations with rational languages</span></h4>
<p>Only operations with rational languages over the same alphabet are allowed.</p>
<p>We may compute expressions for the <code class="code">product</code>, <code class="code">union</code> and <code class="code">star</code> (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 <code class="code">UnionRatExp</code>, <code class="code">ProductRatExp</code>, <code class="code">StarRatExp</code>, that return respectively rational expressions for the <em>union</em> and <em>product</em> of the languages given by the rational expressions <code class="code">r</code> and <code class="code">s</code> and the <code class="code">star</code> of the language given by the rational expression <code class="code">r</code>.</p>
<p><a id="X8206BD4E82A81D8F" name="X8206BD4E82A81D8F"></a></p>
<h5>3.3-1 UnionRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnionRatExp</code>( <var class="Arg">r, s</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><a id="X7E29107587611CE2" name="X7E29107587611CE2"></a></p>
<h5>3.3-2 ProductRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ProductRatExp</code>( <var class="Arg">r, s</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><a id="X83D8DAE6862C8A96" name="X83D8DAE6862C8A96"></a></p>
<h5>3.3-3 StarRatExp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StarRatExp</code>( <var class="Arg">r</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The expression <code class="code">(a(aUb))*</code> may be produced in the following way</p>
<table class="example">
<tr><td><pre>
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))*
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chapA.html">A</a> <a href="chapB.html">B</a> <a href="chapC.html">C</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
519
