This chapter describes some functions involving automata. It starts with functions to obtain equivalent automata of other type. Then the minimalization is considered.
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.
‣ EpsilonToNFA( A ) | ( function ) |
A is an automaton with ϵ-transitions. Returns a NFA recognizing the same language.
gap> x := Automaton("epsilon",3,"ab@",[ [ [ 3 ], [ 1 ], [ 1, 2 ] ], [ [ ], [ ], [ 1, 3 ] ], [ [ 1, 3 ], [ 1 ], [ 3 ] ] ],[ 1, 2, 3 ],[ 1, 3 ]);; gap> Display(x); | 1 2 3 --------------------------------- a | [ 3 ] [ 1 ] [ 1, 2 ] b | [ 1, 3 ] @ | [ 1, 3 ] [ 1 ] [ 3 ] Initial states: [ 1, 2, 3 ] Accepting states: [ 1, 3 ] gap> Display(EpsilonToNFA(x)); | 1 2 3 ------------------------------------ a | [ 3 ] [ 1, 3 ] [ 1 .. 3 ] b | [ 1, 3 .. 3 ] Initial states: [ 1 .. 3 ] Accepting states: [ 1, 2, 3 ]
‣ EpsilonToNFASet( A ) | ( function ) |
A is an automaton with ϵ-transitions. Returns a NFA recognizing the same language. This function differs from EpsilonToNFA (5.1-1) in that it is faster for smaller automata, or automata with few epsilon transitions, but slower in the really hard cases.
‣ EpsilonCompactedAut( A ) | ( function ) |
A is an automaton with ϵ-transitions. Returns an ϵNFA with each strongly-connected component of the epsilon-transitions digraph of A identified with a single state and recognizing the same language.
gap> x := Automaton("epsilon",3,"ab@",[ [ [ ], [ 1 ], [ 1 ] ], [ [ 2 ], [ ], [ ] ], [ [ 2 ], [ 1, 2, 3 ], [ 1, 3 ] ] ],[ 3 ],[ 2, 3 ]);; gap> Display(x); | 1 2 3 ------------------------------------ a | [ 1 ] [ 1 ] b | [ 2 ] @ | [ 2 ] [ 1, 2, 3 ] [ 1, 3 ] Initial state: [ 3 ] Accepting states: [ 2, 3 ] gap> Display(EpsilonCompactedAut(x)); | 1 ----------- a | [ 1 ] b | [ 1 ] @ | Initial state: [ 1 ] Accepting state: [ 1 ]
‣ ReducedNFA( A ) | ( function ) |
A is a non deterministic automaton (without ϵ-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.
gap> x := Automaton("nondet",5,"ab",[ [ [ 2, 5 ], [ 2, 5 ], [ 4 ], [ 5 ], [ 3 ] ], [ [ 1 , 2 ], [ 1, 2, 3, 4 ], [ 1, 2, 3, 5 ], [ 2, 5 ], [ 2, 3 ] ] ],[ 1 ],[ 2, 3, 5 ]);; gap> Display(x); | 1 2 3 4 5 ---------------------------------------------------------------------- a | [ 2, 5 ] [ 2, 5 ] [ 4 ] [ 5 ] [ 3 ] b | [ 1, 2 ] [ 1, 2, 3, 4 ] [ 1, 2, 3, 5 ] [ 2, 5 ] [ 2, 3 ] Initial state: [ 1 ] Accepting states: [ 2, 3, 5 ] gap> Display(ReducedNFA(x)); | 1 2 3 4 5 ---------------------------------------------------------------------- a | [ 3 ] [ 1 ] [ 2 ] [ 1, 4 ] [ 1, 4 ] b | [ 3, 4 ] [ 1, 4 ] [ 1, 3, 4, 5 ] [ 2, 3, 4, 5 ] [ 4, 5 ] Initial state: [ 5 ] Accepting states: [ 1, 3, 4 ]
‣ NFAtoDFA( A ) | ( function ) |
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 [MMP+95] program. The returned automaton is dense deterministic
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 ]
‣ FuseSymbolsAut( A, s1, s2 ) | ( function ) |
Given an automaton A and integers s1 and s2 which, returns an NFA obtained by replacing all transitions through s2 by transitions through s1.
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 ]
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 [AHU74]). 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 [MMP+95] has been very useful.
‣ UsefulAutomaton( A ) | ( function ) |
Given an automaton A (deterministic or not), outputs a dense DFA B whose states are all reachable and such that A and B are equivalent.
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 ]
‣ MinimalizedAut( A ) | ( function ) |
Returns the minimal automaton equivalent to A.
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 ]
‣ MinimalAutomaton( A ) | ( attribute ) |
Returns the minimal automaton equivalent to A, but stores it so that future computations of this automaton just return the stored automaton.
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:
‣ AccessibleStates( aut[, p] ) | ( function ) |
Computes the list of states of the automaton aut which are accessible from state p. When p is not given, returns the states which are accessible from any initial state.
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 ]
‣ AccessibleAutomaton( A ) | ( function ) |
If A is a deterministic automaton, not necessarily dense, an equivalent dense deterministic accessible automaton is returned. (The function UsefulAutomaton is called.)
If A is not deterministic with a single initial state, an equivalent accessible automaton is returned.
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 ]
‣ IntersectionLanguage( A1, A2 ) | ( function ) |
‣ IntersectionAutomaton( A1, A2 ) | ( function ) |
Computes an automaton that recognizes the intersection of the languages given (through automata or rational expressions by) A1 and A2. 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.
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 ]
‣ AutomatonAllPairsPaths( A ) | ( function ) |
Given an automaton A, with n states, outputs a n x n matrix P, such that P[i][j] is the list of simple paths from state i to state j in A.
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 ]
generated by GAPDoc2HTML