6. Some fonctions involving automata

6.1 title

6.1-1 EpsilonToNFA
> EpsilonToNFA( A )( function )

A is an automaton with epsilon-transitions. Returns a NFA recognizing the same language.




6.1-2 NFAtoDFA
> NFAtoDFA( A )( function )

Given an NFA, computes the equivalent DFA, using the powerset construction, according to the algorithm presented in the report of the AMoRE [MM+95] program. The returned automaton is dense deterministic




6.1-3 SubSetAutomaton
> SubSetAutomaton( A )( function )

Is a synonym of NFAtoDFA.




6.1-4 AreEquivAut
> AreEquivAut( A1, A2 )( function )

Tests if the automata A1 and A2 are equivalent, i.e. recognize the same language. This means that the corresponding minimal automata are isomorphic.




6.2 Minimalization of an automaton

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 [AU74]). It is well known (see [HU69]) that it suffices to reduce the automaton given and remove the inaccessible states. Again, the documentation for the computer program AMoRE [MM+95] has been very usefull.

6.2-1 UsefulAutomaton
> UsefulAutomaton( A )( function )

Given an automaton A, outputs a dense DFA B whose states are all reachable and such that L(B)= L(A)).



6.2-2 MinimalizeAut
> MinimalizeAut( A )( function )

returns the minimal automaton equivalent to A.




6.2-3 MinimalizeDDAutomaton
> MinimalizeDDAutomaton( A )( function )

Synonym of MinimalizeAut




6.2-4 MinimalAutomaton
> MinimalAutomaton( A )( attribute )



6.2-5 AccessibleDAutomaton
> AccessibleDAutomaton( A )( function )

A is a deterministic automaton, not necessarily dense; an equivalent dense deterministic accessible automaton is returned.




6.2-6 AccessibleStates
> AccessibleStates( aut, p )( function )

Computes the list of states of the non deterministic automaton aut which are accessible from state p.




6.2-7 AccessibleAutomaton
> AccessibleAutomaton( A )( function )

If A is a deterministic automaton, not necessarily dense, an equivalent dense deterministic accessible automaton is returned. (The function AccessibleDAutomaton is called.)

If A is not deterministic with a single initial state, an equivalent accessible automaton is returned.




6.2-8 ProductAutomaton
> ProductAutomaton( A1, A2 )( function )

The arguments must be deterministic automata. Returns the product of A1 and A2.

Note: (p,q)->(p-1)m+q is a bijection from 1,ldotsm, ntimes 1,..., m to 1,ldotsm,mn.




6.2-9 IntersectionAutomaton
> IntersectionAutomaton( A1, A2 )( function )

The same as ProductAutomaton, but works for all kinds of automata







generated by GAPDoc2HTML