<!-- $Id: aut-func.xml,v 1.12 Exp $ -->
<Chapter><Heading>Some functions involving automata</Heading>
This chapter describes some functions involving automata. It starts with functions to obtain equivalent automata of other type. Then the minimalization is considered.
<Section><Heading>From one type to another</Heading>
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.
<ManSection>
<Func Name="EpsilonToNFA" Arg="A"/>
<Description>
<A>A</A> is an automaton with <M>\epsilon</M>-transitions. Returns a NFA
recognizing the same language.
<Example><![CDATA[
gap> x:=RandomAutomaton("epsilon",3,2);;Display(x);
| 1 2 3
------------------------------------
a | [ 2 ] [ 3 ] [ 2 ]
b | [ 1, 2 ] [ 1, 2 ] [ 1, 3 ]
@ | [ 1, 2 ] [ 1, 2 ] [ 1, 2 ]
Initial states: [ 2, 3 ]
Accepting states: [ 1, 2, 3 ]
gap> Display(EpsilonToNFA(x));
| 1 2 3
------------------------------------------
a | [ 1, 2 ] [ 1, 2, 3 ] [ 1, 2 ]
b | [ 1, 2 ] [ 1, 2 ] [ 1, 2, 3 ]
Initial states: [ 1, 2, 3 ]
Accepting states: [ 1, 2, 3 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="EpsilonToNFASet" Arg="A"/>
<Description>
<A>A</A> is an automaton with <M>\epsilon</M>-transitions. Returns a NFA
recognizing the same language. This function differs from <Ref Func="EpsilonToNFA"/>
in that it is faster for smaller automata, or automata with few
epsilon transitions, but slower in the really hard cases.
</Description>
</ManSection>
<ManSection>
<Func Name="EpsilonCompactedAut" Arg="A"/>
<Description>
<A>A</A> is an automaton with <M>\epsilon</M>-transitions. Returns an
<M>\epsilon</M>NFA with
each strongly-connected component of the
epsilon-transitions digraph of <A>A</A> identified with a single state and
recognizing the same language.
<Example><![CDATA[
gap> x:=RandomAutomaton("epsilon",3,2);;Display(x);
| 1 2 3
------------------------------------
a | [ 1, 2 ] [ 1, 3 ] [ 1, 2 ]
b | [ 1, 2 ] [ 1, 2 ] [ 2, 3 ]
@ | [ 3 ] [ 2 ]
Initial state: [ 3 ]
Accepting states: [ 1, 3 ]
gap> Display(EpsilonCompactedAut(x));
| 1 2
-------------------------
a | [ 1, 2 ] [ 1, 2 ]
b | [ 1, 2 ] [ 1, 2 ]
@ |
Initial state: [ 2 ]
Accepting states: [ 1, 2 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="ReducedNFA" Arg="A"/>
<Description>
<A>A</A> is a non deterministic automaton (without <M>\epsilon</M>-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.
<Example><![CDATA[
gap> x:=RandomAutomaton("nondet",5,2);;Display(x);
| 1 2 3 4 5
----------------------------------------------------------------------
a | [ 1, 5 ] [ 1, 2, 4, 5 ] [ 1, 3, 5 ] [ 3, 4, 5 ] [ 4 ]
b | [ 2, 3, 4 ] [ 3 ] [ 2, 3, 4 ] [ 2, 4, 5 ] [ 3 ]
Initial state: [ 4 ]
Accepting states: [ 1, 3, 4, 5 ]
gap> Display(ReducedNFA(x));
| 1 2 3 4
--------------------------------------------------------
a | [ 1, 3 ] [ 1, 2, 3, 4 ] [ 4 ] [ 1, 3, 4 ]
b | [ 1, 2, 4 ] [ 1 ] [ 1 ] [ 2, 3, 4 ]
Initial state: [ 4 ]
Accepting states: [ 1, 3, 4 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="NFAtoDFA" Arg="A"/>
<Description>
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 <Cite Key="AMORE:95"/> program.
The returned automaton is dense deterministic
<Example><![CDATA[
gap> x:=RandomAutomaton("nondet",3,2);;Display(x);
| 1 2 3
---------------------------
a | [ 2 ] [ 1, 3 ]
b | [ 2, 3 ]
Initial states: [ 1, 3 ]
Accepting states: [ 1, 2 ]
gap> Display(NFAtoDFA(x));
| 1 2 3
--------------
a | 2 2 1
b | 3 3 3
Initial state: [ 1 ]
Accepting states: [ 1, 2, 3 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="FuseSymbolsAut" Arg="A, s1, s2"/>
<Description>
Given an automaton <A>A</A> and integers <A>s1</A> and <A>s2</A> which, returns an NFA
obtained by replacing all transitions through <A>s2</A> by transitions through <A>s1</A>.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",3,2);;Display(x);
| 1 2 3
--------------
a | 2 3
b | 1
Initial state: [ 3 ]
Accepting states: [ 1, 2, 3 ]
gap> Display(FuseSymbolsAut(x,1,2));
| 1 2 3
---------------------------
a | [ 2 ] [ 1, 3 ]
Initial state: [ 3 ]
Accepting states: [ 1, 2, 3 ]
]]></Example>
</Description>
</ManSection>
</Section>
<Section><Heading>Minimalization of an automaton</Heading>
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 <Cite Key="AHU:74"/>). It is well known (see <Cite Key="HU:69"/>) that it suffices
to reduce the automaton given and remove the inaccessible states. Again, the
documentation for the computer program AMoRE <Cite Key="AMORE:95"/> has been very useful.
<ManSection>
<Func Name="UsefulAutomaton" Arg="A"/>
<Description>
Given an automaton <A>A</A> (deterministic or not), outputs a dense DFA <A>B</A> whose states are all reachable and such that <A>A</A> and <A>B</A> are equivalent.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",4,2);;Display(x);
| 1 2 3 4
-----------------
a | 3 4
b | 1 4
Initial state: [ 3 ]
Accepting states: [ 2, 3, 4 ]
gap> Display(UsefulAutomaton(x));
| 1 2 3
--------------
a | 2 3 3
b | 3 3 3
Initial state: [ 1 ]
Accepting states: [ 1, 2 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="MinimalizedAut" Arg="A"/>
<Description>
Returns the minimal automaton equivalent to <A>A</A>.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",4,2);;Display(x);
| 1 2 3 4
-----------------
a | 3 4
b | 1 2 3
Initial state: [ 4 ]
Accepting states: [ 2, 3, 4 ]
gap> Display(MinimalizedAut(x));
| 1 2
-----------
a | 2 2
b | 2 2
Initial state: [ 1 ]
Accepting state: [ 1 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Attr Name=" MinimalAutomaton" Arg="A"/>
<Description>
Returns the minimal automaton equivalent to <A>A</A>, but stores it so that
future computations of this automaton just return the stored automaton.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",4,2);;Display(x);
| 1 2 3 4
-----------------
a | 2 4
b | 3 4
Initial state: [ 4 ]
Accepting states: [ 1, 2, 3 ]
gap> Display(MinimalAutomaton(x));
| 1
--------
a | 1
b | 1
Initial state: [ 1 ]
Accepting state:
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="AccessibleStates" Arg="aut [, p]"/>
<Description>
Computes the list of states of the automaton <A>aut</A>
which are accessible from state <A>p</A>. When <A>p</A> is not given, returns the states which are accessible from any initial state.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",4,2);;Display(x);
| 1 2 3 4
-----------------
a | 1 2 4
b | 2 4
Initial state: [ 2 ]
Accepting states: [ 1, 2, 3 ]
gap> AccessibleStates(x,3);
[ 1, 2, 3, 4 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="AccessibleAutomaton" Arg="A"/>
<Description>
If <A>A</A> is a deterministic automaton, not necessarily dense, an
equivalent dense deterministic accessible automaton is returned.
(The function <C>UsefulAutomaton</C> is called.)
<P/>
If <A>A</A> is not deterministic with a single initial state, an equivalent
accessible automaton is returned.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",4,2);;Display(x);
| 1 2 3 4
-----------------
a | 1 3
b | 1 3 4
Initial state: [ 2 ]
Accepting states: [ 3, 4 ]
gap> Display(AccessibleAutomaton(x));
| 1 2 3 4
-----------------
a | 2 4 4 4
b | 2 3 4 4
Initial state: [ 1 ]
Accepting states: [ 2, 3 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="IntersectionLanguage" Arg="A1,A2"/>
<Func Name="IntersectionAutomaton" Arg="A1,A2"/>
<Description>
Computes an automaton that recognizes the intersection of the languages given (through automata or rational expressions by) <A>A1</A> and <A>A2</A>.
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.
<Example><![CDATA[
gap> x:=RandomAutomaton("det",3,2);;Display(x);
| 1 2 3
--------------
a | 2 3
b | 1
Initial state: [ 3 ]
Accepting states: [ 1, 2, 3 ]
gap> y:=RandomAutomaton("det",3,2);;Display(y);
| 1 2 3
--------------
a | 1
b | 1 3
Initial state: [ 3 ]
Accepting states: [ 1, 3 ]
gap> Display(IntersectionLanguage(x,y));
| 1 2
-----------
a | 2 2
b | 2 2
Initial state: [ 1 ]
Accepting state: [ 1 ]
]]></Example>
</Description>
</ManSection>
<ManSection>
<Func Name="AutomatonAllPairsPaths" Arg="A"/>
<Description>
Given an automaton <A>A</A>, with <C>n</C> states, outputs a <C>n</C> x <C>n</C> matrix P,
such that P[i][j] is the list of simple paths from state i to
state j in <A>A</A>.
<Example><![CDATA[
gap> a:=RandomAutomaton("det",3,2);
< deterministic automaton on 2 letters with 3 states >
gap> AutomatonAllPairsPaths(a);
[ [ [ [ 1, 1 ] ], [ ], [ ] ], [ [ [ 2, 1 ] ], [ [ 2, 2 ] ], [ ] ],
[ [ [ 3, 2, 1 ] ], [ [ 3, 2 ] ], [ [ 3, 3 ] ] ] ]
gap> Display(a);
| 1 2 3
--------------
a | 1 2
b | 1 2 3
Initial state: [ 3 ]
Accepting states: [ 1, 2 ]
]]></Example>
</Description>
</ManSection>
</Section>
</Chapter>
