Quelle chap4_mj.html
Sprache: HTML
products/Sources/formale Sprachen/GAP/pkg/automata/doc/chap4_mj.html
<?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 >
<
script type=
"text/javascript"
src=
"https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML " >
</
script >
<
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" />
<
script src=
"manual.js" type=
"text/javascript" ></
script >
<
script type=
"text/javascript" >overwriteStyle();</
script >
</
head >
<
body class=
"chap4" onload=
"jscontent()" >
<
div class=
"chlinktop" ><
span class=
"chlink1" >Goto Chapter: </
span ><a href=
"chap0_mj.html" >Top<
/a> <a href="chap1_mj.html" >1</a> <a href="chap2_mj.html" >2</a> <a href="chap3_mj.html" >3</a> <a href="chap4_mj.html" >4</a> <a href="chap5_mj.html" >5</a> <a href="chap6_mj.html" >6</a> <a href="chapA_mj.html" >A</a> <a href="chapB_mj.html" >B</a> <a href="chapC_mj.html" >C</a> <a href="chapBib_mj.html" >Bib</a> <a href="chapInd_mj.html" >Ind</a> </div >div class="chlinkprevnexttop" > <a href="chap0_mj.html" >[Top of Book]</a> <a href="chap0_mj.html#contents" >[Contents]</a> <a href="chap3_mj.html" >[Previous Chapter]</a> <a href="chap5_mj.html" >[Next Chapter]</a> </div >"mathjaxlink" class="pcenter" ><a href="chap4.html" >[MathJax off]</a></p>"X7B5CD9B7796BD926" name="X7B5CD9B7796BD926" ></a></p>div class="ChapSects" ><a href="chap4_mj.html#X7B5CD9B7796BD926" >4 <span class="Heading" >Automata <em >versus</em > rational expressions</span ></a>div class="ContSect" ><span class="tocline" ><span class="nocss" > </span ><a href="chap4_mj.html#X7E631B92873300C1" >4.1 <span class="Heading" >From automata to rational expressions</span ></a>span >div class="ContSSBlock" >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X8751E3927CA4DEA1" >4.1-1 AutomatonToRatExp </a></span >div ></div >div class="ContSect" ><span class="tocline" ><span class="nocss" > </span ><a href="chap4_mj.html#X8138227D7E65FC8C" >4.2 <span class="Heading" >From rational expression to automata</span ></a>span >div class="ContSSBlock" >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X840EEB7B7DD8B03D" >4.2-1 RatExpToNDAut</a></span >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X866BCCB2788E8561" >4.2-2 RatExpToAutomaton</a></span >div ></div >div class="ContSect" ><span class="tocline" ><span class="nocss" > </span ><a href="chap4_mj.html#X85DCEFB88712056E" >4.3 <span class="Heading" >span ></a>span >div class="ContSSBlock" >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X84E0143A860889A6" >4.3-1 IsEmptyLang</a></span >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X86AA1A5F7E1EEAFE" >4.3-2 IsFullLang</a></span >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X8346D1B17DBF96E7" >4.3-3 AreEqualLang</a></span >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X7FCB176285FA5BBB" >4.3-4 IsContainedLang</a></span >span class="ContSS" ><br /><span class="nocss" > </span ><a href="chap4_mj.html#X83F1DE067C2D31A5" >4.3-5 AreDisjointLang</a></span >div ></div >div >span class="Heading" >Automata <em >versus</em > rational expressions</span ></h3>ecisely when it may be given by means of a rational expression, i.e. is a rational language.</p>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>"X7E631B92873300C1" name="X7E631B92873300C1" ></a></p>span class="Heading" >From automata to rational expressions</span ></h4>"X8751E3927CA4DEA1" name="X8751E3927CA4DEA1" ></a></p>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 >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>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >x:=Automaton("det" ,4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >FAtoRatExp(x);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >aut:=Automaton("det" ,4,"xy" ,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >FAtoRatExp(aut);</span >pre ></div >"X8138227D7E65FC8C" name="X8138227D7E65FC8C" ></a></p>span class="Heading" >From rational expression to automata</span ></h4>"X840EEB7B7DD8B03D" name="X840EEB7B7DD8B03D" ></a></p>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 >var class="Arg" >R</var >, computes the equivalent NFA</p>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("aUab" );</span span class="GAPprompt" >gap></span > <span class="GAPinput" >Display(RatExpToNDAut(r));</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("xUxy" ); </span span class="GAPprompt" >gap></span > <span class="GAPinput" >Display(RatExpToNDAut(r)); </span >pre ></div >"X866BCCB2788E8561" name="X866BCCB2788E8561" ></a></p>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 >var class="Arg" >R</var >, these functions, which are synonyms, use <code "func" >RatExpToNDAut</code > (<a href="chap4_mj.html#X840EEB7B7DD8B03D" ><span class="RefLink" >4.2-1</span ></a>)) to compute the equivalent NFA and then returns the equivalent minimal DFA</p>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("@U(aUb)(aUb)" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >Display(RatExpToAut(r));</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("@U(0U1)(0U1)" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >Display(RatExpToAut(r)); </span >pre ></div >"X85DCEFB88712056E" name="X85DCEFB88712056E" ></a></p>span class="Heading" >span ></h4>section describes functions that perform tests on automata, rational expressions and their accepted languages.</p>"X84E0143A860889A6" name="X84E0143A860889A6" ></a></p>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 >var class="Arg" > R </var > is the empty language.</p>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r := RationalExpression("empty_set" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsEmptyLang(r);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >r := RationalExpression("aUb" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsEmptyLang(r);</span >pre ></div >"X86AA1A5F7E1EEAFE" name="X86AA1A5F7E1EEAFE" ></a></p>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 >var class="Arg" > R </var > represents the Kleene closure of the alphabet of <var class="Arg" > R </var > .</p>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("aUb" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsFullLang(r);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("(aUb)*" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsFullLang(r);</span >pre ></div >"X8346D1B17DBF96E7" name="X8346D1B17DBF96E7" ></a></p>div class="func" ><table class="func" width="100%" ><tr ><td class="tdleft" ><code class="func" >‣ AreEqualLang</code >( <var class="Arg" >A1</var >, <var class="Arg" >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</var >, <var class="Arg" >A2</var > )</td ><td class="tdright" >( function )</td ></tr ></table ></div >var class="Arg" 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>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >x := Automaton("det" ,4,"ab" ,[ [ 0, 1, 3, 4 ], [ 0, 1, 2, 0 ] ],[ 2 ],[ 1, 2, 3, 4 ] );;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >y := Automaton("det" ,4,"ab" ,[ [ 1, 3, 4, 0 ], [ 0, 3, 4, 0 ] ],[ 3 ],[ 1, 3, 4 ]);;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >z := Automaton("det" ,4,"ab" ,[ [ 0, 4, 0, 0 ], [ 1, 3, 4, 0 ] ],[ 2 ],[ 1, 3, 4 ]);;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreEquivAut(x, y);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreEquivAut(x, z);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >a:=RationalExpression("(aUb)*ab*" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >b:=RationalExpression("(aUb)*" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreEqualLang(a, b);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >a:=RationalExpression("(bUa)*" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreEqualLang(a, b);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >x:=RationalExpression("(1U0)*" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreEqualLang(a, x); </span >pre ></div >"X7FCB176285FA5BBB" name="X7FCB176285FA5BBB" ></a></p>div class="func" ><table class="func" width="100%" ><tr ><td class="tdleft" ><code class="func" >‣ IsContainedLang</code >( <var class="Arg" >R1</var >, <var class="Arg" >R2</var > )</td ><td class="tdright" >( function )</td ></tr ></table ></div >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>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("aUab" );</span span class="GAPprompt" >gap></span > <span class="GAPinput" >s:=RationalExpression("a" ,"ab" );</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsContainedLang(s,r);</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >IsContainedLang(r,s);</span >pre ></div >"X83F1DE067C2D31A5" name="X83F1DE067C2D31A5" ></a></p>div class="func" ><table class="func" width="100%" ><tr ><td class="tdleft" ><code class="func" >‣ AreDisjointLang</code >( <var class="Arg" >R1</var >, <var class="Arg" >R2</var > )</td ><td class="tdright" >( function )</td ></tr ></table ></div >var class="Arg" > R1 </var > and <var class="Arg" > R2 </var > are disjoint.</p>div class="example" ><pre >span class="GAPprompt" >gap></span > <span class="GAPinput" >r:=RationalExpression("aUab" );;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >s:=RationalExpression("a" ,"ab" );;</span >span class="GAPprompt" >gap></span > <span class="GAPinput" >AreDisjointLang(r,s);</span >pre ></div >div class="chlinkprevnextbot" > <a href="chap0_mj.html" >[Top of Book]</a> <a href="chap0_mj.html#contents" >[Contents]</a> <a href="chap3_mj.html" >[Previous Chapter]</a> <a href="chap5_mj.html" >[Next Chapter]</a> </div >div class="chlinkbot" ><span class="chlink1" >Goto Chapter: </span ><a href="chap0_mj.html" >Top</a> <a href="chap1_mj.html" >1</a> <a href="chap2_mj.html" >2</a> <a href="chap3_mj.html" >3</a> <a href="chap4_mj.html" >4</a> <a href="chap5_mj.html" >5</a> <a href="chap6_mj.html" >6</a> <a href="chapA_mj.html" >A</a> <a href="chapB_mj.html" >B</a> <a href="chapC_mj.html" >C</a> <a href="chapBib_mj.html" >Bib</a> <a href="chapInd_mj.html" >Ind</a> </div >hr />"foot" >generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc " >GAPDoc2HTML</a></p>body >html > Messung V0.5 in Prozent C=100 H=100 G=100
¤ Dauer der Verarbeitung: 0.18 Sekunden
(vorverarbeitet am 2026-04-25)
¤ *© Formatika GbR, Deutschland
2026-05-26
