5 Some functions involving automata This chapter describes some functions involving automata. It starts with functions to obtain equivalent automata of other type. Then the minimalization is considered. 5.1 From one type to another 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. 5.1-1 EpsilonToNFA EpsilonToNFA( A )  function A is an automaton with ϵ-transitions. Returns a NFA recognizing the same language.  Example  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 ]  5.1-2 EpsilonToNFASet 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. 5.1-3 EpsilonCompactedAut 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.  Example  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 ]  5.1-4 ReducedNFA 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.  Example  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 ]  5.1-5 NFAtoDFA 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 [MMPTV95] program. The returned automaton is dense deterministic  Example  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 ]  5.1-6 FuseSymbolsAut 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.  Example  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 ]  5.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 [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 [MMPTV95] has been very useful. 5.2-1 UsefulAutomaton 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.  Example  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 ]  5.2-2 MinimalizedAut MinimalizedAut( A )  function Returns the minimal automaton equivalent to A.  Example  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 ]  5.2-3 MinimalAutomaton  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.  Example  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:  5.2-4 AccessibleStates 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.  Example  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 ]  5.2-5 AccessibleAutomaton 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.  Example  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 ]  5.2-6 IntersectionLanguage 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.  Example  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 ]  5.2-7 AutomatonAllPairsPaths 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.  Example  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 ]