<p>This chapter describes some functions involving automata. It starts with functions to obtain equivalent automata of other type. Then the minimalization is considered.</p>
<h4>5.1 <span class="Heading">From one type to another</span></h4>
<p>Recall that two automata are said to be equivalent when they recognize the same language. Next we have functions which have as input automata of one type and as output equivalent automata of another type.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpsilonToNFA</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is an automaton with <span class="SimpleMath">ϵ</span>-transitions. Returns a NFA recognizing the same language.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpsilonToNFASet</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is an automaton with <span class="SimpleMath">ϵ</span>-transitions. Returns a NFA recognizing the same language. This function differs from <code class="func">EpsilonToNFA</code> (<a href="chap5.html#X81E06D518428CA3C"><span class="RefLink">5.1-1</span></a>) in that it is faster for smaller automata, or automata with few epsilon transitions, but slower in the really hard cases.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpsilonCompactedAut</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is an automaton with <span class="SimpleMath">ϵ</span>-transitions. Returns an <span class="SimpleMath">ϵ</span>NFA with each strongly-connected component of the epsilon-transitions digraph of <var class="Arg">A</var> identified with a single state and recognizing the same language.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedNFA</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">A</var> is a non deterministic automaton (without <span class="SimpleMath">ϵ</span>-transitions). Returns an NFA accepting the same language as its input but with possibly fewer states (it quotients out by the smallest right-invariant partition of the states). A paper describing the algorithm is in preparation.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NFAtoDFA</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given an NFA, these synonym functions, compute the equivalent DFA, using the powerset construction, according to the algorithm presented in the report of the AMoRE <a href="chapBib.html#biBAMORE:95">[MMP+95]</a> program. The returned automaton is dense deterministic</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FuseSymbolsAut</code>( <var class="Arg">A</var>, <var class="Arg">s1</var>, <var class="Arg">s2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given an automaton <var class="Arg">A</var> and integers <var class="Arg">s1</var> and <var class="Arg">s2</var> which, returns an NFA obtained by replacing all transitions through <var class="Arg">s2</var> by transitions through <var class="Arg">s1</var>.</p>
<h4>5.2 <span class="Heading">Minimalization of an automaton</span></h4>
<p>The algorithm used to minimalize a dense deterministic automaton (i.e., to compute a dense minimal automaton recognizing the same language) is based on an algorithm due to Hopcroft (see <a href="chapBib.html#biBAHU:74">[AHU74]</a>). It is well known (see <a href="chapBib.html#biBHU:69">[HU69]</a>) that it suffices to reduce the automaton given and remove the inaccessible states. Again, the documentation for the computer program AMoRE <a href="chapBib.html#biBAMORE:95">[MMP+95]</a> has been very useful.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UsefulAutomaton</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given an automaton <var class="Arg">A</var> (deterministic or not), outputs a dense DFA <var class="Arg">B</var> whose states are all reachable and such that <var class="Arg">A</var> and <var class="Arg">B</var> are equivalent.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalAutomaton</code>( <var class="Arg">A</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns the minimal automaton equivalent to <var class="Arg">A</var>, but stores it so that future computations of this automaton just return the stored automaton.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AccessibleStates</code>( <var class="Arg">aut</var>[, <var class="Arg">p</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Computes the list of states of the automaton <var class="Arg">aut</var> which are accessible from state <var class="Arg">p</var>. When <var class="Arg">p</var> is not given, returns the states which are accessible from any initial state.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AccessibleAutomaton</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>If <var class="Arg">A</var> is a deterministic automaton, not necessarily dense, an equivalent dense deterministic accessible automaton is returned. (The function <code class="code">UsefulAutomaton</code> is called.)</p>
<p>If <var class="Arg">A</var> is not deterministic with a single initial state, an equivalent accessible automaton is returned.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IntersectionLanguage</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">‣ IntersectionAutomaton</code>( <var class="Arg">A1</var>, <var class="Arg">A2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Computes an automaton that recognizes the intersection of the languages given (through automata or rational expressions by) <var class="Arg">A1</var> and <var class="Arg">A2</var>. When the arguments are deterministic automata, is the same as ProductAutomaton, but works for all kinds of automata. Note that the language of the product of two automata is precisely the intersection of the languages of the automata.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutomatonAllPairsPaths</code>( <var class="Arg">A</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given an automaton <var class="Arg">A</var>, with <code class="code">n</code> states, outputs a <code class="code">n</code> x <code class="code">n</code> matrix P, such that P[i][j] is the list of simple paths from state i to state j in <var class="Arg">A</var>.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
