[1X5 Some functions involving automata[0X This chapter describes some functions involving automata. It starts with functions to obtain equivalent automata of other type. Then the minimalization is considered. [1X5.1 From one type to another[0X 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. [1X5.1-1 EpsilonToNFA[0m [2X> EpsilonToNFA( [0X[3XA[0X[2X ) ________________________________________________[0Xfunction [3XA[0m is an automaton with epsilon-transitions. Returns a NFA recognizing the same language. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("epsilon",3,2);;Display(x);[0X [4X | 1 2 3[0X [4X------------------------------------[0X [4X a | [ 2 ] [ 3 ] [ 2 ][0X [4X b | [ 1, 2 ] [ 1, 2 ] [ 1, 3 ][0X [4X @ | [ 1, 2 ] [ 1, 2 ] [ 1, 2 ][0X [4XInitial states: [ 2, 3 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> Display(EpsilonToNFA(x));[0X [4X | 1 2 3[0X [4X------------------------------------------[0X [4X a | [ 1, 2 ] [ 1, 2, 3 ] [ 1, 2 ][0X [4X b | [ 1, 2 ] [ 1, 2 ] [ 1, 2, 3 ][0X [4XInitial states: [ 1, 2, 3 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4X------------------------------------------------------------------[0X [1X5.1-2 EpsilonToNFASet[0m [2X> EpsilonToNFASet( [0X[3XA[0X[2X ) _____________________________________________[0Xfunction [3XA[0m is an automaton with epsilon-transitions. Returns a NFA recognizing the same language. This function differs from [2XEpsilonToNFA[0m ([14X5.1-1[0m) in that it is faster for smaller automata, or automata with few epsilon transitions, but slower in the really hard cases. [1X5.1-3 EpsilonCompactedAut[0m [2X> EpsilonCompactedAut( [0X[3XA[0X[2X ) _________________________________________[0Xfunction [3XA[0m is an automaton with epsilon-transitions. Returns an epsilonNFA with each strongly-connected component of the epsilon-transitions digraph of [3XA[0m identified with a single state and recognizing the same language. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("epsilon",3,2);;Display(x);[0X [4X | 1 2 3[0X [4X------------------------------------[0X [4X a | [ 1, 2 ] [ 1, 3 ] [ 1, 2 ][0X [4X b | [ 1, 2 ] [ 1, 2 ] [ 2, 3 ][0X [4X @ | [ 3 ] [ 2 ][0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 3 ][0X [4Xgap> Display(EpsilonCompactedAut(x));[0X [4X | 1 2[0X [4X-------------------------[0X [4X a | [ 1, 2 ] [ 1, 2 ][0X [4X b | [ 1, 2 ] [ 1, 2 ][0X [4X @ |[0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 1, 2 ][0X [4X------------------------------------------------------------------[0X [1X5.1-4 ReducedNFA[0m [2X> ReducedNFA( [0X[3XA[0X[2X ) __________________________________________________[0Xfunction [3XA[0m is a non deterministic automaton (without epsilon-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. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("nondet",5,2);;Display(x);[0X [4X | 1 2 3 4 5[0X [4X----------------------------------------------------------------------[0X [4X a | [ 1, 5 ] [ 1, 2, 4, 5 ] [ 1, 3, 5 ] [ 3, 4, 5 ] [ 4 ][0X [4X b | [ 2, 3, 4 ] [ 3 ] [ 2, 3, 4 ] [ 2, 4, 5 ] [ 3 ][0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 3, 4, 5 ][0X [4Xgap> Display(ReducedNFA(x));[0X [4X | 1 2 3 4[0X [4X--------------------------------------------------------[0X [4X a | [ 1, 3 ] [ 1, 2, 3, 4 ] [ 4 ] [ 1, 3, 4 ][0X [4X b | [ 1, 2, 4 ] [ 1 ] [ 1 ] [ 2, 3, 4 ][0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 3, 4 ][0X [4X------------------------------------------------------------------[0X [1X5.1-5 NFAtoDFA[0m [2X> NFAtoDFA( [0X[3XA[0X[2X ) ____________________________________________________[0Xfunction 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 [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("nondet",3,2);;Display(x);[0X [4X | 1 2 3[0X [4X---------------------------[0X [4X a | [ 2 ] [ 1, 3 ][0X [4X b | [ 2, 3 ][0X [4XInitial states: [ 1, 3 ][0X [4XAccepting states: [ 1, 2 ][0X [4Xgap> Display(NFAtoDFA(x));[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 2 2 1[0X [4X b | 3 3 3[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4X------------------------------------------------------------------[0X [1X5.1-6 FuseSymbolsAut[0m [2X> FuseSymbolsAut( [0X[3XA, s1, s2[0X[2X ) ______________________________________[0Xfunction Given an automaton [3XA[0m and integers [3Xs1[0m and [3Xs2[0m which, returns an NFA obtained by replacing all transitions through [3Xs2[0m by transitions through [3Xs1[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",3,2);;Display(x);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 2 3[0X [4X b | 1[0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> Display(FuseSymbolsAut(x,1,2));[0X [4X | 1 2 3[0X [4X---------------------------[0X [4X a | [ 2 ] [ 1, 3 ][0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4X------------------------------------------------------------------[0X [1X5.2 Minimalization of an automaton[0X 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. [1X5.2-1 UsefulAutomaton[0m [2X> UsefulAutomaton( [0X[3XA[0X[2X ) _____________________________________________[0Xfunction Given an automaton [3XA[0m (deterministic or not), outputs a dense DFA [3XB[0m whose states are all reachable and such that [3XA[0m and [3XB[0m are equivalent. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",4,2);;Display(x);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 3 4[0X [4X b | 1 4[0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 2, 3, 4 ][0X [4Xgap> Display(UsefulAutomaton(x));[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 2 3 3[0X [4X b | 3 3 3[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 1, 2 ][0X [4X------------------------------------------------------------------[0X [1X5.2-2 MinimalizedAut[0m [2X> MinimalizedAut( [0X[3XA[0X[2X ) ______________________________________________[0Xfunction Returns the minimal automaton equivalent to [3XA[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",4,2);;Display(x);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 3 4[0X [4X b | 1 2 3[0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 2, 3, 4 ][0X [4Xgap> Display(MinimalizedAut(x));[0X [4X | 1 2[0X [4X-----------[0X [4X a | 2 2[0X [4X b | 2 2[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 1 ][0X [4X------------------------------------------------------------------[0X [1X5.2-3 MinimalAutomaton[0m [2X> MinimalAutomaton( [0X[3XA[0X[2X ) __________________________________________[0Xattribute Returns the minimal automaton equivalent to [3XA[0m, but stores it so that future computations of this automaton just return the stored automaton. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",4,2);;Display(x);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 2 4[0X [4X b | 3 4[0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> Display(MinimalAutomaton(x));[0X [4X | 1[0X [4X--------[0X [4X a | 1[0X [4X b | 1[0X [4XInitial state: [ 1 ][0X [4XAccepting state:[0X [4X------------------------------------------------------------------[0X [1X5.2-4 AccessibleStates[0m [2X> AccessibleStates( [0X[3Xaut[, p][0X[2X ) _____________________________________[0Xfunction Computes the list of states of the automaton [3Xaut[0m which are accessible from state [3Xp[0m. When [3Xp[0m is not given, returns the states which are accessible from any initial state. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",4,2);;Display(x);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 1 2 4[0X [4X b | 2 4[0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> AccessibleStates(x,3);[0X [4X[ 1, 2, 3, 4 ][0X [4X------------------------------------------------------------------[0X [1X5.2-5 AccessibleAutomaton[0m [2X> AccessibleAutomaton( [0X[3XA[0X[2X ) _________________________________________[0Xfunction If [3XA[0m is a deterministic automaton, not necessarily dense, an equivalent dense deterministic accessible automaton is returned. (The function [10XUsefulAutomaton[0m is called.) If [3XA[0m is not deterministic with a single initial state, an equivalent accessible automaton is returned. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",4,2);;Display(x);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 1 3[0X [4X b | 1 3 4[0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 3, 4 ][0X [4Xgap> Display(AccessibleAutomaton(x));[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 2 4 4 4[0X [4X b | 2 3 4 4[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 2, 3 ][0X [4X------------------------------------------------------------------[0X [1X5.2-6 IntersectionLanguage[0m [2X> IntersectionLanguage( [0X[3XA1, A2[0X[2X ) ___________________________________[0Xfunction [2X> IntersectionAutomaton( [0X[3XA1, A2[0X[2X ) __________________________________[0Xfunction Computes an automaton that recognizes the intersection of the languages given (through automata or rational expressions by) [3XA1[0m and [3XA2[0m. 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. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=RandomAutomaton("det",3,2);;Display(x);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 2 3[0X [4X b | 1[0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 2, 3 ][0X [4Xgap> y:=RandomAutomaton("det",3,2);;Display(y);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1[0X [4X b | 1 3[0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 3 ][0X [4Xgap> Display(IntersectionLanguage(x,y));[0X [4X | 1 2[0X [4X-----------[0X [4X a | 2 2[0X [4X b | 2 2[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 1 ][0X [4X------------------------------------------------------------------[0X [1X5.2-7 AutomatonAllPairsPaths[0m [2X> AutomatonAllPairsPaths( [0X[3XA[0X[2X ) ______________________________________[0Xfunction Given an automaton [3XA[0m, with [10Xn[0m states, outputs a [10Xn[0m x [10Xn[0m matrix P, such that P[i][j] is the list of simple paths from state i to state j in [3XA[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RandomAutomaton("det",3,2);[0X [4X< deterministic automaton on 2 letters with 3 states >[0X [4Xgap> AutomatonAllPairsPaths(a);[0X [4X[ [ [ [ 1, 1 ] ], [ ], [ ] ], [ [ [ 2, 1 ] ], [ [ 2, 2 ] ], [ ] ],[0X [4X [ [ [ 3, 2, 1 ] ], [ [ 3, 2 ] ], [ [ 3, 3 ] ] ] ][0X [4Xgap> Display(a);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 2[0X [4X b | 1 2 3[0X [4XInitial state: [ 3 ][0X [4XAccepting states: [ 1, 2 ][0X [4X------------------------------------------------------------------[0X