[1X2 Finite Automata[0X This chapter describes the representations used in this package for finite automata and some functions to determine information about them. We have to remark that the states of an automaton are always named 1,2,3,...; the alphabet may be given by the user. By default it is {a,b,c,...} (or {a_1,a_2,a_3,...} in the case of alphabets with more than 27 letters). The transition function of an automaton with q states over an alphabet with n letters is represented by a (not necessarily dense) nx q matrix. Each row of the matrix describes the action of the corresponding letter on the states. In the case of a [13Xdeterministic automaton[0m (DFA) the entries of the matrix are non-negative integers. When all entries of the transition table are positive integers, the automaton is said to be [13Xdense[0m or [13Xcomplete[0m. In the case of a [13Xnon deterministic automaton[0m (NFA) the entries of the matrix may be lists of non-negative integers. [13XAutomata with epsilon-transitions[0m are also allowed: the last letter of the alphabet is assumed to be epsilon and is represented by @. [1X2.1 Automata generation[0X The way to create an automaton in [5XGAP[0m is the following [1X2.1-1 Automaton[0m [2X> Automaton( [0X[3XType, Size, Alphabet, TransitionTable, Initial, Accepting[0X[2X ) [0Xfunction [10XType[0m may be [10X"det"[0m, [10X"nondet"[0m or [10X"epsilon"[0m according to whether the automaton is deterministic, non deterministic or an automaton with epsilon-transitions. [10XSize[0m is a positive integer representing the number of states of the automaton. [10XAlphabet[0m is the number of letters of the alphabet or a list with the letters of the ordered alphabet. [10XTransitionTable[0m is the transition matrix. The entries are non-negative integers not greater than the size of the automaton. In the case of non deterministic automata, lists of non-negative integers not greater than the size of the automaton are also allowed. [10XInitial[0m and [10XAccepting[0m are, respectively, the lists of initial and accepting states. [4X--------------------------- Example ----------------------------[0X [4X[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,4]],[1],[4]);[0X [4X< deterministic automaton on 2 letters with 4 states >[0X [4Xgap> Display(aut);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 3 3 4[0X [4X b | 3 4 4[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 4 ][0X [4X[0X [4X------------------------------------------------------------------[0X The alphabet of the automaton may be specified: [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,"01",[[3,,3,4],[3,4,0,4]],[1],[4]);[0X [4X< deterministic automaton on 2 letters with 4 states >[0X [4Xgap> Display(aut);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X 0 | 3 3 4[0X [4X 1 | 3 4 4[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 4 ][0X [4X------------------------------------------------------------------[0X Instead of leaving a hole in the transition matrix, we may write a [10X0[0m to mean that no transition is present. Non deterministic automata may be given the same way. [4X--------------------------- Example ----------------------------[0X [4Xgap> ndaut:=Automaton("nondet",4,2,[[3,[1,2],3,0],[3,4,0,[2,3]]],[1],[4]);[0X [4X< non deterministic automaton on 2 letters with 4 states >[0X [4Xgap> Display(ndaut);[0X [4X | 1 2 3 4[0X [4X-----------------------------------------[0X [4X a | [ 3 ] [ 1, 2 ] [ 3 ][0X [4X b | [ 3 ] [ 4 ] [ 2, 3 ][0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 4 ][0X [4X------------------------------------------------------------------[0X Also in the same way can be given epsilon-automata. The letter epsilon is written [10X@[0m instead. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("epsilon",3,"01@",[[,[2],[3]],[[1,3],,[1]],[[1],[2],[0X [4X> [2]]],[2],[2,3]);[0X [4X< epsilon automaton on 3 letters with 3 states >[0X [4Xgap> Display(x);[0X [4X | 1 2 3[0X [4X------------------------------[0X [4X 0 | [ 2 ] [ 3 ][0X [4X 1 | [ 1, 3 ] [ 1 ][0X [4X @ | [ 1 ] [ 2 ] [ 2 ][0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 2, 3 ][0X [4X------------------------------------------------------------------[0X Bigger automata are displayed in another form: [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",16,2,[[4,0,0,6,3,1,4,8,7,4,3,0,6,1,6,0],[0X [4X> [3,4,0,0,6,1,0,6,1,6,1,6,6,4,8,7,4,5]],[1],[4]);[0X [4X< deterministic automaton on 2 letters with 16 states >[0X [4Xgap> Display(aut);[0X [4X1 a 4[0X [4X1 b 3[0X [4X2 b 4[0X [4X ... some more lines[0X [4X15 a 6[0X [4X15 b 8[0X [4X16 b 7[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 4 ][0X [4X------------------------------------------------------------------[0X [1X2.1-2 IsAutomaton[0m [2X> IsAutomaton( [0X[3XO[0X[2X ) _________________________________________________[0Xfunction In the presence of an object [3XO[0m, one may want to test whether [10XO[0m is an automaton. This may be done using the function [10XIsAutomaton[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X [4Xgap> IsAutomaton(x);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.1-3 IsDeterministicAutomaton[0m [2X> IsDeterministicAutomaton( [0X[3Xaut[0X[2X ) __________________________________[0Xfunction Returns [9Xtrue[0m when [10Xaut[0m is a deterministic automaton and [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X [4Xgap> IsDeterministicAutomaton(x);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.1-4 IsNonDeterministicAutomaton[0m [2X> IsNonDeterministicAutomaton( [0X[3Xaut[0X[2X ) _______________________________[0Xfunction Returns [9Xtrue[0m when [10Xaut[0m is a non deterministic automaton and [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> y:=Automaton("nondet",3,2,[[,[1,3],],[,[2,3],[1,3]]],[1,2],[1,3]);;[0X [4Xgap> IsNonDeterministicAutomaton(y);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.1-5 IsEpsilonAutomaton[0m [2X> IsEpsilonAutomaton( [0X[3Xaut[0X[2X ) ________________________________________[0Xfunction Returns [9Xtrue[0m when [10Xaut[0m is an epsilon-automaton and [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;[0X [4Xgap> IsEpsilonAutomaton(z);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.1-6 String[0m [2X> String( [0X[3Xaut[0X[2X ) ____________________________________________________[0Xfunction The way [5XGAP[0m displays an automaton is quite natural, but when one wants to do small changes, for example using [13Xcopy/paste[0m, the use of the function [10XString[0m (possibly followed by [10XPrint[0m) may be usefull. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X [4Xgap> String(x);[0X [4X"Automaton(\"det\",3,\"ab\",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;"[0X [4Xgap> Print(String(x));[0X [4XAutomaton("det",3,"ab",[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X [4X------------------------------------------------------------------[0X [4X--------------------------- Example ----------------------------[0X [4Xgap> z:=Automaton("epsilon",2,2,[[[1,2],],[[2],[1]]],[1,2],[1,2]);;[0X [4Xgap> Print(String(z));[0X [4XAutomaton("epsilon",2,"a@",[ [ [ 1, 2 ], [ ] ], [ [ 2 ], [ 1 ] ] ],[ 1, 2 ],[ \[0X [4X1, 2 ]);;[0X [4X------------------------------------------------------------------[0X [1X2.1-7 RandomAutomaton[0m [2X> RandomAutomaton( [0X[3XType, Size, Alphabet[0X[2X ) __________________________[0Xfunction Given the [3XType[0m, the [3XSize[0m (i.e. the number of states) and the [3XAlphabet[0m (a positive integer or a list), returns a pseudo random automaton with these parameters. [4X--------------------------- Example ----------------------------[0X [4Xgap> RandomAutomaton("det",5,"ac");[0X [4X< deterministic automaton on 2 letters with 5 states >[0X [4Xgap> Display(last);[0X [4X | 1 2 3 4 5[0X [4X--------------------[0X [4X a | 2 3[0X [4X c | 2 3[0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 3, 4 ][0X [4X[0X [4Xgap> RandomAutomaton("nondet",3,["a","b","c"]);[0X [4X< non deterministic automaton on 3 letters with 3 states >[0X [4X[0X [4Xgap> RandomAutomaton("epsilon",2,"abc");[0X [4X< epsilon automaton on 4 letters with 2 states >[0X [4X[0X [4Xgap> RandomAutomaton("epsilon",2,2);[0X [4X< epsilon automaton on 3 letters with 2 states >[0X [4Xgap> Display(last);[0X [4X | 1 2[0X [4X----------------------[0X [4X a | [ 1, 2 ][0X [4X b | [ 2 ] [ 1 ][0X [4X @ | [ 1, 2 ][0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 1, 2 ][0X [4X[0X [4Xgap> a:=RandomTransformation(3);;[0X [4Xgap> b:=RandomTransformation(3);;[0X [4Xgap> aut:=RandomAutomaton("det",4,[a,b]);[0X [4X< deterministic automaton on 2 letters with 4 states >[0X [4X------------------------------------------------------------------[0X [1X2.2 Automata internals[0X In this section we describe the functions used to access the internals of an automaton. [1X2.2-1 AlphabetOfAutomaton[0m [2X> AlphabetOfAutomaton( [0X[3Xaut[0X[2X ) _______________________________________[0Xfunction Returns the number of symbols in the alphabet of automaton [10Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> AlphabetOfAutomaton(aut);[0X [4X2[0X [4X------------------------------------------------------------------[0X [1X2.2-2 AlphabetOfAutomatonAsList[0m [2X> AlphabetOfAutomatonAsList( [0X[3Xaut[0X[2X ) _________________________________[0Xfunction Returns the alphabet of automaton [10Xaut[0m always as a list. Note that when the alphabet of the automaton is given as an integer (meaning the number of symbols) less than 27 it returns the list [10X"abcd...."[0m. If the alphabet is given by means of an integer greater than 27, the function returns [10X[ "a1", "a2", "a3", "a4", ... ][0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> a:=RandomAutomaton("det",5,"cat");[0X [4X< deterministic automaton on 3 letters with 5 states >[0X [4Xgap> AlphabetOfAutomaton(a);[0X [4X3[0X [4Xgap> AlphabetOfAutomatonAsList(a);[0X [4X"cat"[0X [4Xgap> a:=RandomAutomaton("det",5,20);[0X [4X< deterministic automaton on 20 letters with 5 states >[0X [4Xgap> AlphabetOfAutomaton(a);[0X [4X20[0X [4Xgap> AlphabetOfAutomatonAsList(a);[0X [4X"abcdefghijklmnopqrst"[0X [4Xgap> a:=RandomAutomaton("det",5,30);[0X [4X< deterministic automaton on 30 letters with 5 states >[0X [4Xgap> AlphabetOfAutomaton(a);[0X [4X30[0X [4Xgap> AlphabetOfAutomatonAsList(a);[0X [4X[ "a1", "a2", "a3", "a4", "a5", "a6", "a7", "a8", "a9", "a10", "a11", [0X [4X "a12", "a13", "a14", "a15", "a16", "a17", "a18", "a19", "a20", "a21",[0X [4X "a22", "a23", "a24", "a25", "a26", "a27", "a28", "a29", "a30" ][0X [4X------------------------------------------------------------------[0X [1X2.2-3 TransitionMatrixOfAutomaton[0m [2X> TransitionMatrixOfAutomaton( [0X[3Xaut[0X[2X ) _______________________________[0Xfunction Returns the transition matrix of automaton [10Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> TransitionMatrixOfAutomaton(aut);[0X [4X[ [ 3, 0, 3, 4 ], [ 3, 4, 0, 0 ] ][0X [4X------------------------------------------------------------------[0X [1X2.2-4 InitialStatesOfAutomaton[0m [2X> InitialStatesOfAutomaton( [0X[3Xaut[0X[2X ) __________________________________[0Xfunction Returns the initial states of automaton [10Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> InitialStatesOfAutomaton(aut);[0X [4X[ 1 ][0X [4X------------------------------------------------------------------[0X [1X2.2-5 SetInitialStatesOfAutomaton[0m [2X> SetInitialStatesOfAutomaton( [0X[3Xaut, I[0X[2X ) ____________________________[0Xfunction Sets the initial states of automaton [10Xaut[0m. [10XI[0m may be a positive integer or a list of positive integers. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> SetInitialStatesOfAutomaton(aut,4);[0X [4Xgap> InitialStatesOfAutomaton(aut);[0X [4X[ 4 ][0X [4Xgap> SetInitialStatesOfAutomaton(aut,[2,3]);[0X [4Xgap> InitialStatesOfAutomaton(aut);[0X [4X[ 2, 3 ][0X [4X------------------------------------------------------------------[0X [1X2.2-6 FinalStatesOfAutomaton[0m [2X> FinalStatesOfAutomaton( [0X[3Xaut[0X[2X ) ____________________________________[0Xfunction Returns the final states of automaton [10Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> FinalStatesOfAutomaton(aut);[0X [4X[ 4 ][0X [4X------------------------------------------------------------------[0X [1X2.2-7 SetFinalStatesOfAutomaton[0m [2X> SetFinalStatesOfAutomaton( [0X[3Xaut, F[0X[2X ) ______________________________[0Xfunction Sets the final states of automaton [10Xaut[0m. [10XF[0m may be a positive integer or a list of positive integers. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> FinalStatesOfAutomaton(aut);[0X [4X[ 4 ][0X [4Xgap> SetFinalStatesOfAutomaton(aut,2);[0X [4Xgap> FinalStatesOfAutomaton(aut);[0X [4X[ 2 ][0X [4X------------------------------------------------------------------[0X [1X2.2-8 NumberStatesOfAutomaton[0m [2X> NumberStatesOfAutomaton( [0X[3Xaut[0X[2X ) ___________________________________[0Xfunction Returns the number of states of automaton [10Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> NumberStatesOfAutomaton(aut);[0X [4X4[0X [4X------------------------------------------------------------------[0X [1X2.3 Comparison of automata[0X Although there is no standard way to compare automata it is usefull to be able to do some kind of comparison. Doing so, one can consider sets of automata. We just compare the strings of the automata. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 0 ], [ 0, 1, 0 ] ],[ 3 ],[ 2 ]);;[0X [4Xgap> y:=Automaton("det",3,2,[ [ 2, 0, 0 ], [ 1, 3, 0 ] ],[ 3 ],[ 2, 3 ]);;[0X [4Xgap> x=y;[0X [4Xfalse[0X [4Xgap> Size(Set([y,x,x]));[0X [4X2[0X [4X------------------------------------------------------------------[0X [1X2.4 Tests involving automata[0X This section describes some useful tests involving automata. [1X2.4-1 IsDenseAutomaton[0m [2X> IsDenseAutomaton( [0X[3Xaut[0X[2X ) __________________________________________[0Xfunction Tests whether a deterministic automaton [10Xaut[0m is complete. (See also [2XNullCompletionAutomaton[0m ([14X2.5-2[0m).) [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[3,4,0,]],[1],[4]);;[0X [4Xgap> IsDenseAutomaton(aut); [0X [4Xfalse[0X [4X------------------------------------------------------------------[0X [1X2.4-2 IsRecognizedByAutomaton[0m [2X> IsRecognizedByAutomaton( [0X[3XA, w[0X[2X ) __________________________________[0Xfunction The argments are: an automaton [3XA[0m and a string (i.e. a word) [3Xw[0m in the alphabet of the automaton. Returns [10Xtrue[0m if the word is recognized by the automaton and [10Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",3,2,[[1,2,1],[2,1,3]],[1],[2]);;[0X [4Xgap> IsRecognizedByAutomaton(aut,"bbb");[0X [4Xtrue[0X [4X[0X [4Xgap> aut:=Automaton("det",3,"01",[[1,2,1],[2,1,3]],[1],[2]);;[0X [4Xgap> IsRecognizedByAutomaton(aut,"111");[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.4-3 IsPermutationAutomaton[0m [2X> IsPermutationAutomaton( [0X[3Xaut[0X[2X ) ____________________________________[0Xfunction The argument is a deterministic automaton. Returns [9Xtrue[0m when each letter of the alphabet induces a permutation on the vertices and [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X [4Xgap> IsPermutationAutomaton(x);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.4-4 IsInverseAutomaton[0m [2X> IsInverseAutomaton( [0X[3Xaut[0X[2X ) ________________________________________[0Xfunction The argument is a deterministic automaton. Returns [9Xtrue[0m when each letter of the alphabet induces an injective partial function on the vertices and [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 1, 2 ] ],[ 2 ],[ 1 ]);;[0X [4Xgap> IsInverseAutomaton(x);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X Frequently an inverse automaton is thought as if the inverse edges (labeled by formal inverses of the letters of the alphabet) were present, although they are usually not explicited. They can be made explicit using the function [10XAddInverseEdgesToInverseAutomaton[0m [1X2.4-5 AddInverseEdgesToInverseAutomaton[0m [2X> AddInverseEdgesToInverseAutomaton( [0X[3Xaut[0X[2X ) _________________________[0Xfunction The argument is an inverse automaton over the alphabet {a,b,c,...}. Returns an automaton with the inverse edges added. (The formal inverse of a letter is represented by the corresponding capital letter.) [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[[ 0, 1, 3 ],[ 0, 1, 2 ]],[ 2 ],[ 1 ]);;Display(x);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 1 2[0X [4XInitial state: [ 2 ][0X [4XAccepting state: [ 1 ][0X [4Xgap> AddInverseEdgesToInverseAutomaton(x);Display(x);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 1 2[0X [4X A | 2 3[0X [4X B | 2 3[0X [4XInitial state: [ 2 ][0X [4XAccepting state: [ 1 ][0X [4X------------------------------------------------------------------[0X [1X2.4-6 IsReversibleAutomaton[0m [2X> IsReversibleAutomaton( [0X[3Xaut[0X[2X ) _____________________________________[0Xfunction The argument is a deterministic automaton. Returns [9Xtrue[0m when [3Xaut[0m is a reversible automaton, i.e. the automaton obtained by reversing all edges and switching the initial and final states (see also [2XReversedAutomaton[0m ([14X2.5-5[0m)) is deterministic. Returns [9Xfalse[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 1, 2 ], [ 0, 1, 3 ] ],[ 2 ],[ 2 ]);;[0X [4Xgap> IsReversibleAutomaton(x);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X2.5 Basic operations[0X [1X2.5-1 CopyAutomaton[0m [2X> CopyAutomaton( [0X[3Xaut[0X[2X ) _____________________________________________[0Xfunction Returns a new automaton, which is a copy of automaton [3Xaut[0m. [1X2.5-2 NullCompletionAutomaton[0m [2X> NullCompletionAutomaton( [0X[3Xaut[0X[2X ) ___________________________________[0Xfunction [10Xaut[0m is a deterministic automaton. If it is complete returns [3Xaut[0m, otherwise returns the completion (with a null state) of [3Xaut[0m. Notice that the words recognized by [3Xaut[0m and its completion are the same. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut:=Automaton("det",4,2,[[3,,3,4],[2,4,4,]],[1],[4]);;[0X [4Xgap> IsDenseAutomaton(aut);[0X [4Xfalse[0X [4Xgap> y:=NullCompletionAutomaton(aut);;Display(y);[0X [4X | 1 2 3 4 5[0X [4X--------------------[0X [4X a | 3 5 3 4 5[0X [4X b | 2 4 4 5 5[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 4 ][0X [4X------------------------------------------------------------------[0X The state added is a [13Xsink state[0m i.e. it is a state q which is not initial nor accepting and for all letter a in the alphabet of the automaton, q is the result of the action of a in q. (Notice that reading a word, one does not go out of a sink state.) [1X2.5-3 ListSinkStatesAut[0m [2X> ListSinkStatesAut( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction Computes the list of all sink states of the automaton [3Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X [4Xgap> ListSinkStatesAut(x);[0X [4X[ ][0X [4Xgap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;[0X [4Xgap> ListSinkStatesAut(y);[0X [4X[ 3 ][0X [4X------------------------------------------------------------------[0X [1X2.5-4 RemovedSinkStates[0m [2X> RemovedSinkStates( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction Removes all sink states of the automaton [3Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> y:=Automaton("det",3,2,[[ 2, 3, 3 ],[ 1, 2, 3 ]],[ 1 ],[ 2 ]);;Display(y);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 2 3 3[0X [4X b | 1 2 3[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 2 ][0X [4Xgap> x := RemovedSinkStates(y);Display(x);[0X [4X< deterministic automaton on 2 letters with 2 states >[0X [4X | 1 2[0X [4X-----------[0X [4X a | 2[0X [4X b | 1 2[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 2 ][0X [4X------------------------------------------------------------------[0X [1X2.5-5 ReversedAutomaton[0m [2X> ReversedAutomaton( [0X[3Xaut[0X[2X ) _________________________________________[0Xfunction Inverts the arrows of the automaton [3Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> y:=Automaton("det",3,2,[ [ 2, 3, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2 ]);;[0X [4Xgap> z:=ReversedAutomaton(y);;Display(z);[0X [4X | 1 2 3[0X [4X------------------------------[0X [4X a | [ 1 ] [ 2, 3 ][0X [4X b | [ 1 ] [ 2 ] [ 3 ][0X [4XInitial state: [ 2 ][0X [4XAccepting state: [ 1 ][0X [4X------------------------------------------------------------------[0X [1X2.5-6 PermutedAutomaton[0m [2X> PermutedAutomaton( [0X[3Xaut, p[0X[2X ) ______________________________________[0Xfunction Given an automaton [3Xaut[0m and a list [3Xp[0m representing a permutation of the states, outputs the equivalent permuted automaton. [4X--------------------------- Example ----------------------------[0X [4Xgap> y:=Automaton("det",4,2,[[2,3,4,2],[0,0,0,1]],[1],[3]);;Display(y);[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 2 3 4 2[0X [4X b | 1[0X [4XInitial state: [ 1 ][0X [4XAccepting state: [ 3 ][0X [4Xgap> Display(PermutedAutomaton(y, [3,2,4,1]));[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 2 4 2 1[0X [4X b | 3[0X [4XInitial state: [ 3 ][0X [4XAccepting state: [ 4 ][0X [4X------------------------------------------------------------------[0X [1X2.5-7 ListPermutedAutomata[0m [2X> ListPermutedAutomata( [0X[3Xaut[0X[2X ) ______________________________________[0Xfunction Given an automaton [3Xaut[0m, returns a list of automata with permuted states [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 0, 2, 3 ], [ 1, 2, 3 ] ],[ 1 ],[ 2, 3 ]);;[0X [4Xgap> ListPermutedAutomata(x);[0X [4X[ < deterministic automaton on 2 letters with 3 states >, [0X [4X< deterministic automaton on 2 letters with[0X [4X 3 states >, < deterministic automaton on 2 letters with 3 states >,[0X [4X < deterministic automaton on 2 letters with 3 states >, [0X [4X< deterministic automaton on 2 letters with[0X [4X 3 states >, < deterministic automaton on 2 letters with 3 states > ][0X [4X------------------------------------------------------------------[0X [1X2.5-8 NormalizedAutomaton[0m [2X> NormalizedAutomaton( [0X[3XA[0X[2X ) _________________________________________[0Xfunction Produces an equivalent automaton but in which the initial state is numbered 1 and the accepting states have the greatest numbers. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[[ 1, 2, 0 ],[ 0, 1, 2 ]],[2],[1, 2]);;Display(x);[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 2[0X [4X b | 1 2[0X [4XInitial state: [ 2 ][0X [4XAccepting states: [ 1, 2 ][0X [4Xgap> Display(NormalizedAutomaton(x));[0X [4X | 1 2 3[0X [4X--------------[0X [4X a | 1 3[0X [4X b | 3 1[0X [4XInitial state: [ 1 ][0X [4XAccepting states: [ 3, 1 ][0X [4X------------------------------------------------------------------[0X [1X2.5-9 UnionAutomata[0m [2X> UnionAutomata( [0X[3XA, B[0X[2X ) ____________________________________________[0Xfunction Produces the disjoint union of the deterministic or non deterministic automata [10XA[0m and [10XB[0m. The output is a non-deterministic automaton. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;[0X [4Xgap> y:=Automaton("det",3,2,[ [ 0, 1, 3 ], [ 0, 0, 0 ] ],[ 1 ],[ 1, 2, 3 ]);;[0X [4Xgap> UnionAutomata(x,y);[0X [4X< non deterministic automaton on 2 letters with 6 states >[0X [4Xgap> Display(last);[0X [4X | 1 2 3 4 5 6[0X [4X------------------------------------------------[0X [4X a | [ 1 ] [ 2 ] [ 4 ] [ 6 ][0X [4X b | [ 1 ] [ 2 ][0X [4XInitial states: [ 2, 4 ][0X [4XAccepting states: [ 1, 2, 4, 5, 6 ][0X [4X------------------------------------------------------------------[0X [1X2.5-10 ProductAutomaton[0m [2X> ProductAutomaton( [0X[3XA1, A2[0X[2X ) _______________________________________[0Xfunction The arguments must be deterministic automata. Returns the product of [3XA1[0m and [3XA2[0m. Note: (p,q)->(p-1)m+q is a bijection from {1,..., n}x {1,..., m} to {1,...,mn}. [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> z:=ProductAutomaton(x, y);;Display(z);[0X [4X | 1 2 3 4 5 6 7 8 9[0X [4X--------------------------------[0X [4X a | 4 7[0X [4X b | 1 3[0X [4XInitial state: [ 9 ][0X [4XAccepting states: [ 1, 3, 4, 6, 7, 9 ][0X [4X------------------------------------------------------------------[0X [1X2.5-11 ProductOfLanguages[0m [2X> ProductOfLanguages( [0X[3XA1, A2[0X[2X ) _____________________________________[0Xfunction Given two regular languages (as automata or rational expressions), returns an automaton that recognizes the concatenation of the given languages, that is, the set of words uv such that u belongs to the first language and v belongs to the second language. [4X--------------------------- Example ----------------------------[0X [4Xgap> a1:=ListOfWordsToAutomaton("ab",["aa","bb"]);[0X [4X< deterministic automaton on 2 letters with 5 states >[0X [4Xgap> a2:=ListOfWordsToAutomaton("ab",["a","b"]);[0X [4X< deterministic automaton on 2 letters with 3 states >[0X [4Xgap> ProductOfLanguages(a1,a2);[0X [4X< deterministic automaton on 2 letters with 5 states >[0X [4Xgap> FAtoRatExp(last);[0X [4X(bbUaa)(aUb)[0X [4X------------------------------------------------------------------[0X [1X2.6 Links with Semigroups[0X Each letter of the alphabet of an automaton induces a partial transformation in its set of states. The semigroup generated by these transformations is called the [13Xtransition semigroup[0m of the automaton. [1X2.6-1 TransitionSemigroup[0m [2X> TransitionSemigroup( [0X[3Xaut[0X[2X ) _______________________________________[0Xfunction Returns the transition semigroup of the deterministic automaton [3Xaut[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> aut := Automaton("det",10,2,[[7,5,7,5,4,9,10,9,10,9],[0X [4X> [8,6,8,9,9,1,3,1,9,9]],[2],[6,7,8,9,10]);;[0X [4Xgap> s := TransitionSemigroup(aut);; [0X [4Xgap> Size(s); [0X [4X30[0X [4X------------------------------------------------------------------[0X The transition semigroup of the minimal automaton recognizing a language is the {\it syntactic semigroup} of that language. [1X2.6-2 SyntacticSemigroupAut[0m [2X> SyntacticSemigroupAut( [0X[3Xaut[0X[2X ) _____________________________________[0Xfunction Returns the syntactic semigroup of the deterministic automaton [3Xaut[0m (i.e. the transition semigroup of the equivalent minimal automaton) when it is non empty and returns [9Xfail[0m otherwise. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",3,2,[ [ 1, 2, 0 ], [ 0, 1, 2 ] ],[ 2 ],[ 1, 2 ]);;[0X [4Xgap> S:=SyntacticSemigroupAut(x);;[0X [4Xgap> Size(S);[0X [4X3[0X [4X------------------------------------------------------------------[0X [1X2.6-3 SyntacticSemigroupLang[0m [2X> SyntacticSemigroupLang( [0X[3Xrat[0X[2X ) ____________________________________[0Xfunction Returns the syntactic semigroup of the language given by the rational expression [3Xrat[0m. [4X--------------------------- Example ----------------------------[0X [4Xgap> rat := RationalExpression("a*ba*ba*(@Ub)");;[0X [4Xgap> S:=SyntacticSemigroupLang(rat);;[0X [4Xgap> Size(S);[0X [4X7[0X [4X------------------------------------------------------------------[0X