<?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 4: Automata versus rational expressions</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="chap3.html">Previous Chapter</a> <a href="chap5.html">Next Chapter</a> </div> <p><a id="X7B5CD9B7796BD926" name="X7B5CD9B7796BD926"></a></p> <div class="ChapSects"><a href="chap4.html#X7B5CD9B7796BD926">4 <span class="Heading">Automata <em>versus</em> rational expressions</span></a> <div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X7E631B92873300C1">4.1 <span class="Heading">From automata to rational expressions</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8751E3927CA4DEA1">4.1-1 AutomatonToRatExp </a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X8138227D7E65FC8C">4.2 <span class="Heading">From rational expression to automata</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X840EEB7B7DD8B03D">4.2-1 RatExpToNDAut</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X866BCCB2788E8561">4.2-2 RatExpToAutomaton</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X85DCEFB88712056E">4.3 <span class="Heading"> Some tests on automata </span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X84E0143A860889A6">4.3-1 IsEmptyLang</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X86AA1A5F7E1EEAFE">4.3-2 IsFullLang</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8346D1B17DBF96E7">4.3-3 AreEqualLang</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7FCB176285FA5BBB">4.3-4 IsContainedLang</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X83F1DE067C2D31A5">4.3-5 AreDisjointLang</a></span> </div> </div> <h3>4 <span class="Heading">Automata <em>versus</em> rational expressions</span></h3> <p>A remarkable theorem due to Kleene shows that a language is recognized by a finite automaton precisely when it may be given by means of a rational expression, i.e. is a rational language.</p> <p>An automaton and a rational expression are said to be <em>equivalent</em> when both represent the same language. In this chapter we describe functions to go from automata to equivalent rational expressions and <em>vice-versa</em>.</p> <p><a id="X7E631B92873300C1" name="X7E631B92873300C1"></a></p> <h4>4.1 <span class="Heading">From automata to rational expressions</span></h4> <p><a id="X8751E3927CA4DEA1" name="X8751E3927CA4DEA1"></a></p> <h5>4.1-1 AutomatonToRatExp </h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AutomatonToRatExp </code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AutToRatExp</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FAtoRatExp</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>From a finite automaton, <code class="code">FAtoRatExp</code>, <code class="code">AutToRatExp</code> and <code class="code">AutomatonToRatExp</code>, which are synonyms, compute one equivalent rational expression, using the state elimination algorithm.</p> <table class="example"> <tr><td><pre> gap> x:=Automaton("det",4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);; gap> FAtoRatExp(x); (aUb)(aUb)U@ gap> aut:=Automaton("det",4,"xy",[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);; gap> FAtoRatExp(aut); (xUy)(xUy)U@ </pre></td></tr></table> <p><a id="X8138227D7E65FC8C" name="X8138227D7E65FC8C"></a></p> <h4>4.2 <span class="Heading">From rational expression to automata</span></h4> <p><a id="X840EEB7B7DD8B03D" name="X840EEB7B7DD8B03D"></a></p> <h5>4.2-1 RatExpToNDAut</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RatExpToNDAut</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Given a rational expression <var class="Arg">R</var>, computes the equivalent NFA</p> <table class="example"> <tr><td><pre> gap> r:=RationalExpression("aUab"); aUab gap> Display(RatExpToNDAut(r)); | 1 2 3 4 -------------------------------- a | [ 1, 2 ] b | [ 3 ] Initial state: [ 4 ] Accepting states: [ 1, 3 ] gap> r:=RationalExpression("xUxy"); xUxy gap> Display(RatExpToNDAut(r)); | 1 2 3 4 -------------------------------- x | [ 1, 2 ] y | [ 3 ] Initial state: [ 4 ] Accepting states: [ 1, 3 ] </pre></td></tr></table> <p><a id="X866BCCB2788E8561" name="X866BCCB2788E8561"></a></p> <h5>4.2-2 RatExpToAutomaton</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RatExpToAutomaton</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RatExpToAut</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Given a rational expression <var class="Arg">R</var>, these functions, which are synonyms, use <code class="func">RatExpToNDAut</code> (<a href="chap4.html#X840EEB7B7DD8B03D"><b>4.2-1</b></a>)) to compute the equivalent NFA and then returns the equivalent minimal DFA</p> <table class="example"> <tr><td><pre> gap> r:=RationalExpression("@U(aUb)(aUb)"); @U(aUb)(aUb) gap> Display(RatExpToAut(r)); | 1 2 3 4 ----------------- a | 3 1 3 2 b | 3 1 3 2 Initial state: [ 4 ] Accepting states: [ 1, 4 ] gap> r:=RationalExpression("@U(0U1)(0U1)"); @U(0U1)(0U1) gap> Display(RatExpToAut(r)); | 1 2 3 4 ----------------- 0 | 3 1 3 2 1 | 3 1 3 2 Initial state: [ 4 ] Accepting states: [ 1, 4 ] </pre></td></tr></table> <p><a id="X85DCEFB88712056E" name="X85DCEFB88712056E"></a></p> <h4>4.3 <span class="Heading"> Some tests on automata </span></h4> <p>This section describes functions that perform tests on automata, rational expressions and their accepted languages.</p> <p><a id="X84E0143A860889A6" name="X84E0143A860889A6"></a></p> <h5>4.3-1 IsEmptyLang</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsEmptyLang</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>This function tests if the language given through a rational expression or an automaton <var class="Arg"> R </var> is the empty language.</p> <table class="example"> <tr><td><pre> gap> r:=RandomRatExp(2); empty_set gap> IsEmptyLang(r); true gap> r:=RandomRatExp(2); aUb gap> IsEmptyLang(r); false </pre></td></tr></table> <p><a id="X86AA1A5F7E1EEAFE" name="X86AA1A5F7E1EEAFE"></a></p> <h5>4.3-2 IsFullLang</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFullLang</code>( <var class="Arg">R</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>This function tests if the language given through a rational expression or an automaton <var class="Arg"> R </var> represents the Kleene closure of the alphabet of <var class="Arg"> R </var> .</p> <table class="example"> <tr><td><pre> gap> r:=RationalExpression("aUb"); aUb gap> IsFullLang(r); false gap> r:=RationalExpression("(aUb)*"); (aUb)* gap> IsFullLang(r); true </pre></td></tr></table> <p><a id="X8346D1B17DBF96E7" name="X8346D1B17DBF96E7"></a></p> <h5>4.3-3 AreEqualLang</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AreEqualLang</code>( <var class="Arg">A1, A2</var> )</td><td class="tdright">( function )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AreEquivAut</code>( <var class="Arg">A1, A2</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>These functions, which are synonyms, test if the automata or rational expressions <var class="Arg">A1</var> and <var class="Arg">A2</var> are equivalent, i.e. represent the same language. This is performed by checking that the corresponding minimal automata are isomorphic. Note hat this cannot happen if the alphabets are different.</p> <table class="example"> <tr><td><pre> gap> y:=RandomAutomaton("det",4,2);; gap> x:=RandomAutomaton("det",4,2);; gap> AreEquivAut(x, y); false gap> a:=RationalExpression("(aUb)*ab*"); (aUb)*ab* gap> b:=RationalExpression("(aUb)*"); (aUb)* gap> AreEqualLang(a, b); false gap> a:=RationalExpression("(bUa)*"); (bUa)* gap> AreEqualLang(a, b); true gap> x:=RationalExpression("(1U0)*"); (1U0)* gap> AreEqualLang(a, x); The given languages are not over the same alphabet false g</pre></td></tr></table> <p><a id="X7FCB176285FA5BBB" name="X7FCB176285FA5BBB"></a></p> <h5>4.3-4 IsContainedLang</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsContainedLang</code>( <var class="Arg">R1, R2</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Tests if the language represented (through an automaton or a rational expression) by <var class="Arg"> R1 </var> is contained in the language represented (through an automaton or a rational expression) by <var class="Arg"> R2 </var> .</p> <table class="example"> <tr><td><pre> gap> r:=RationalExpression("aUab"); aUab gap> s:=RationalExpression("a","ab"); a gap> IsContainedLang(s,r); true gap> IsContainedLang(r,s); false </pre></td></tr></table> <p><a id="X83F1DE067C2D31A5" name="X83F1DE067C2D31A5"></a></p> <h5>4.3-5 AreDisjointLang</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AreDisjointLang</code>( <var class="Arg">R1, R2</var> )</td><td class="tdright">( function )</td></tr></table></div> <p>Tests if the languages represented (through automata or a rational expressions) by <var class="Arg"> R1 </var> and <var class="Arg"> R2 </var> are disjoint.</p> <table class="example"> <tr><td><pre> gap> r:=RationalExpression("aUab");; gap> s:=RationalExpression("a","ab");; gap> AreDisjointLang(r,s); false </pre></td></tr></table> <div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap3.html">Previous Chapter</a> <a href="chap5.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>