GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
############################################################################# ## #W aut-def.gi Manuel Delgado <[email protected]> #W Jose Morais <[email protected]> ## ## #H @(#)$Id: aut-def.gi,v 1.13 $ ## #Y Copyright (C) 2004, CMUP, Universidade do Porto, Portugal ## ############################################################################# ## ## This file contains some generic methods for automata. ## ############################################################################# ## ## ## Example ## gap> A:=Automaton("det",4,2,[[3,3,3,4],[3,4,3,4]],[1],[4]); ## < deterministic automaton on 2 letters with 4 states > ## gap> Display(A); ## | 1 2 3 4 ## ----------------- ## a | 3 3 3 4 ## b | 3 4 3 4 ## Initial state: [ 1 ] ## Accepting state: [ 4 ] ## ## The first component of a non deterministic automaton is <"nondet"> ## and that of an epsilon automaton is <"epsilon">. ## ## In the case of automata with e-transitions, the last line of the ## transition table corresponds to the e-transitions (i.e., epsilon is ## considered the last letter of the alphabet). ############################################################################# ## #R ## The transitions of a deterministic automaton are always represented by ## a matrix that may be dense or ## not. If it is dense, the automaton is dense deterministic. ## The holes in the list may be replaced by zeros. ## ## The nondeterministic automata may be represented the same way, with ## sets of states instead of states in the transition matrix. ## ## In order to use this representation for epsilon-automata, an extra letter ## must be added to the alphabet. ## ############################################################################ DeclareRepresentation( "IsAutomatonRep", IsComponentObjectRep, ["type","states","alphabet","transitions","initial","accepting"]); ###################################################################### ## #F Automaton(Type, Size, Alphabet, TransitionTable, ListInitial, ## ListAccepting ) ## ## Produces an automaton ## The Alphabet may be given as a list of symbols (e.g. "xy" or "01") ## or as an integer, representing its size. In the latter case, the alphabet ## is taken as "abc..." (or "a_1,a_2,a_3,..." for an alphabet of more than ## 26 symbols. ## The meaning of the other arguments is clear. ## InstallGlobalFunction( Automaton, function(Type, Size, Alphabet, TransitionTable, ListInitial, ListAccepting ) # local F, alph, j, i, TT, y, x, aut, alphabet, states, # initial, accepting, transitions, A; local A, alph, aut, F, i, j, x, y, TT, l; #some tests... if not IsPosInt(Size) then Error("The size of the automaton must be a positive integer"); elif not (IsPosInt(Alphabet) or IsList(Alphabet)) then Error("The size of the alphabet must be a positive integer or a list"); fi; # Construct the family of all automata. F:= NewFamily( "Automata" , IsAutomatonObj ); if IsPosInt(Alphabet) then if Alphabet < 27 then alph := (List([1..Alphabet], i -> jascii[68+i])); else alph := (List([1..Alphabet], i -> Concatenation("a", String(i)))); fi; if Type = "epsilon" then alph[Length(alph)] := '@'; fi; F!.alphabet := alph; else if Type = "epsilon" then if not Alphabet[Length(Alphabet)] = '@' then Error("The last letter of the alphabet must be @"); fi; j:=0; for i in Alphabet do if i = '@' then j := j + 1; fi; od; if j > 1 then Error("The alphabet must contain only one @"); fi; fi; F!.alphabet := Alphabet; Alphabet := Length(F!.alphabet); fi; if not IsList(TransitionTable) then Error("The transition table must be given as a matrix"); elif not IsList(ListInitial) then Error("The initial states must be provided as a list"); elif not IsList(ListAccepting) then Error("The accepting states must be provided as a list"); elif (Length(TransitionTable) <> Alphabet) then Error("The number of rows of the transition table matrix must equal the size of the alphabet"); fi; #The type of the automaton: deterministic or not must be given if Type <> "det" and Type <> "nondet" and Type <> "epsilon" then Error( "Please specify the type of the automaton as \"det\" or \"nondet\" or \"epsilon\""); fi; # Fill the holes in the transition table with <0> in the case of # deterministic automata and with <[0]> in the case of non # deterministic automata TT := NullMat(Alphabet,Size); for i in [1 .. Alphabet] do for j in[1 .. Size] do if Type = "det" then if IsBound(TransitionTable[i][j]) then if IsInt(TransitionTable[i][j]) then if TransitionTable[i][j] > Size or TransitionTable[i][j] < 0 then Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must be in [0 .. ", String(Size), "]")); else TT[i][j] := TransitionTable[i][j]; fi; else Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must be an integer")); fi; else TT[i][j] := 0; fi; else if IsBound(TransitionTable[i][j]) then if IsInt(TransitionTable[i][j]) then if TransitionTable[i][j] > Size or TransitionTable[i][j] < 0 then Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must be in [0 .. ", String(Size), "]")); else if TransitionTable[i][j] = 0 then TT[i][j] := []; else TT[i][j] := [TransitionTable[i][j]]; fi; fi; elif IsRowVector(TransitionTable[i][j]) then for y in [1 .. Length(TransitionTable[i][j])] do if not IsBound(TransitionTable[i][j][y]) then Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must have all elements in [1 .. ", String(Size), "]")); elif IsPosInt(TransitionTable[i][j][y]) then x := TransitionTable[i][j][y]; if x > Size or x < 0 then Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must have all elements in [1 .. ", String(Size), "]")); fi; elif TransitionTable[i][j][y] = 0 then Unbind(TransitionTable[i][j][y]); else Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must have all elements in [1 .. ", String(Size), "]")); fi; od; TT[i][j] := TransitionTable[i][j]; elif not TransitionTable[i][j] = [] then Error(Concatenation("TransitionTable[", String(i), "][", String(j), "] must be in [0 .. ", String(Size), "]")); else TT[i][j] := TransitionTable[i][j]; fi; else TT[i][j] := []; fi; fi; od; od; aut := rec(type := Type, alphabet := Alphabet, states := Size, initial := ListInitial, accepting := ListAccepting, transitions := TT ); A := Objectify( NewType( F, IsAutomatonObj and IsAutomatonRep and IsAttributeStoringRep ), aut ); # Return the automaton. return A; end); ############################################################################# ## #M ViewObj( <A> ) . . . . . . . . . . . print automata ## InstallMethod( ViewObj, "displays an automaton", true, [IsAutomatonObj and IsAutomatonRep], 0, function( A ) if A!.type = "det" then Print("< deterministic automaton on ", A!.alphabet, " letters with ", A!.states, " states >"); elif A!.type = "nondet" then Print("< non deterministic automaton on ", A!.alphabet, " letters with ", A!.states, " states >"); else Print("< epsilon automaton on ", A!.alphabet, " letters with ", A!.states, " states >"); fi; end); ############################################################################# ## #M PrintObj( <A> ) . . . . . . . . . . . print automata ## InstallMethod( PrintObj, "displays an automaton", true, [IsAutomatonObj and IsAutomatonRep], 0, function( A ) Print(String(A),"\n"); end); ############################################################################# ## #M Display( <A> ) . . . . . . . . . . . print automata ## InstallMethod( Display, "displays an automaton", true, [IsAutomatonObj and IsAutomatonRep], 0, function( A ) local letters, i, str, a, xs, xout, q, lsizeq, sizeq, len, j; letters := []; for i in AlphabetOfAutomatonAsList(A) do Add(letters, [i]); od; if A!.states < 10 then if A!.type = "det" then str := " | "; for i in [1 .. A!.states] do str := Concatenation(str, String(i), " "); od; str := Concatenation(str, "\n-----"); for i in [1 .. A!.states] do str := Concatenation(str, "---"); od; str := Concatenation(str, "\n"); for a in [1 .. A!.alphabet] do xs := ""; xout := OutputTextString(xs, false); PrintTo(xout, letters[a]); str := Concatenation(str, " ", xs, " | "); CloseStream(xout); for i in [1 .. A!.states] do q := A!.transitions[a][i]; if q = 0 then str := Concatenation(str, " "); else str := Concatenation(str, String(q)," "); fi; od; str := Concatenation(str, "\n"); od; if IsBound(A!.accepting[2]) then xs := ""; xout := OutputTextString(xs, false); PrintTo(xout, A!.initial); str := Concatenation(str, "Initial state: ", String(xs), "\n"); CloseStream(xout); xs := ""; xout := OutputTextString(xs, false); PrintTo(xout, A!.accepting); str := Concatenation(str, "Accepting states: ", xs, "\n"); CloseStream(xout); else xs := ""; xout := OutputTextString(xs, false); PrintTo(xout, A!.initial); str := Concatenation(str, "Initial state: ", xs, "\n"); CloseStream(xout); xs := ""; xout := OutputTextString(xs, false); PrintTo(xout, A!.accepting); str := Concatenation(str, "Accepting state: ", xs, "\n"); CloseStream(xout); fi; elif A!.type = "nondet" then lsizeq := []; for i in [1 .. A!.states] do sizeq := 0; for a in [1 .. A!.alphabet] do len := Length(A!.transitions[a][i]); if len > sizeq then sizeq := len; fi; od; sizeq := sizeq + 2*(sizeq-1) + 4; lsizeq[i] := sizeq; od; str := " | "; for i in [1 .. A!.states-1] do str := Concatenation(str, String(i), " "); for j in [1 .. lsizeq[i]] do str := Concatenation(str, " "); od; od; str := Concatenation(str, String(A!.states), "\n---"); for i in [1 .. A!.states] do str := Concatenation(str, "---"); for j in [1 .. lsizeq[i]] do str := Concatenation(str, "-"); od; od; str := Concatenation(str, "\n"); for a in [1 .. A!.alphabet] do str := Concatenation(str, " ", letters[a], " | "); for i in [1 .. A!.states] do q := A!.transitions[a][i]; if q = [] then str := Concatenation(str, " "); for j in [1 .. lsizeq[i]] do str := Concatenation(str, " "); od; else str := Concatenation(str, String(q)," "); len := Length(q); len := len + 2*(len-1) + 4; for j in [len .. lsizeq[i]] do str := Concatenation(str, " "); od; fi; od; str := Concatenation(str, "\n"); od; if IsBound(A!.initial[2]) then if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); elif A!.accepting = [] then str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); else str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; elif A!.initial = [] then if IsBound(A!.accepting[2]) then str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); elif A!.accepting = [] then else str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; else if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); elif A!.accepting = [] then str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); else str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; fi; else lsizeq := []; for i in [1 .. A!.states] do sizeq := 0; for a in [1 .. A!.alphabet] do len := Length(A!.transitions[a][i]); if len > sizeq then sizeq := len; fi; od; sizeq := sizeq + 2*(sizeq-1) + 4; lsizeq[i] := sizeq; od; str := " | "; for i in [1 .. A!.states-1] do str := Concatenation(str, String(i), " "); for j in [1 .. lsizeq[i]] do str := Concatenation(str, " "); od; od; str := Concatenation(str, String(A!.states), "\n---"); for i in [1 .. A!.states] do str := Concatenation(str, "---"); for j in [1 .. lsizeq[i]] do str := Concatenation(str, "-"); od; od; str := Concatenation(str, "\n"); for a in [1 .. A!.alphabet-1] do str := Concatenation(str, " ", letters[a], " | "); for i in [1 .. A!.states] do q := A!.transitions[a][i]; if q = [] then str := Concatenation(str, " "); for j in [1 .. lsizeq[i]] do str := Concatenation(str, " "); od; else str := Concatenation(str, String(q)," "); len := Length(q); len := len + 2*(len-1) + 4; for j in [len .. lsizeq[i]] do str := Concatenation(str, " "); od; fi; od; str := Concatenation(str, "\n"); od; a := A!.alphabet; str := Concatenation(str, " @ | "); for i in [1 .. A!.states] do q := A!.transitions[a][i]; if q = [] then str := Concatenation(str, " "); for j in [1 .. lsizeq[i]] do str := Concatenation(str, " "); od; else str := Concatenation(str, String(q)," "); len := Length(q); len := len + 2*(len-1) + 4; for j in [len .. lsizeq[i]] do str := Concatenation(str, " "); od; fi; od; str := Concatenation(str, "\n"); if IsBound(A!.initial[2]) then if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); else str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; else if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); else str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; fi; fi; else sizeq := Length(String(A!.states)); if A!.type = "det" then str := ""; for i in [1 .. A!.states] do for a in [1 .. A!.alphabet] do q := A!.transitions[a][i]; if q > 0 then str := Concatenation(str, String(i)); for j in [Length(String(i)) .. sizeq] do str := Concatenation(str, " "); od; str := Concatenation(str, " ", letters[a], " ", String(q), "\n"); fi; od; od; if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); else str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; elif A!.type = "nondet" or A!.type = "epsilon" then str := ""; for i in [1 .. A!.states] do for a in [1 .. A!.alphabet] do q := A!.transitions[a][i]; if IsBound(q[1]) then str := Concatenation(str, String(i)); for j in [Length(String(i)) .. sizeq] do str := Concatenation(str, " "); od; str := Concatenation(str, " ", letters[a], " ", String(q), "\n"); fi; od; od; if IsBound(A!.initial[2]) then if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); else str := Concatenation(str, "Initial states: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; else if IsBound(A!.accepting[2]) then str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting states: ", String(A!.accepting), "\n"); else str := Concatenation(str, "Initial state: ", String(A!.initial), "\n"); str := Concatenation(str, "Accepting state: ", String(A!.accepting), "\n"); fi; fi; fi; fi; Print(str); end); ############################################################################# ## #F IsAutomaton(A) ## ## Tests if A is an automaton ## InstallGlobalFunction( IsAutomaton, function(A) return(IsAutomatonObj(A)); end); ############################################################################# ## #F RandomAutomaton(T, Q, A) ## ## Given the type T, number of states Q and number of the input alphabet ## symbols A, this function returns a pseudo random automaton with those ## parameters. To obtain an epsilon automata with 3 non-@-letters plus @, use ## RandomAutomaton("epsilon",2,"abc"); ## < epsilon automaton on 4 letters with 2 states > ## ## InstallGlobalFunction(RandomAutomaton, function(T, Q, A) local i, transitions, a; if not IsPosInt(Q) then Error("The number of states must be a positive integer"); fi; if not (IsPosInt(A) or IsList(A)) then Error("The number of symbols of the input alphabet must be a positive integer or a string"); fi; if IsPosInt(A) then a := A; else a := ShallowCopy(A); A := Length(a); fi; if T = "det" then transitions := []; for i in [1 .. A] do transitions[i] := SSortedList(List([1 .. Q], i -> Random([0 .. Q]))); od; return(Automaton(T, Q, a, transitions, [Random([1 .. Q])], SSortedList(List([1 .. Q], j -> Random([1 .. Q]))))); elif T = "nondet" then transitions := []; for i in [1 .. A] do transitions[i] := List([1 .. Q], i -> SSortedList(List([1 .. Random([0 .. Q])], j -> Random([1 .. Q])))); od; return(Automaton(T, Q, a, transitions, SSortedList(List([1 .. Random([1 .. Q])], j -> Random([1 .. Q]))), SSortedList(List([1 .. Q], j -> Random([1 .. Q]))))); else transitions := []; for i in [1 .. A+1] do transitions[i] := List([1 .. Q], i -> SSortedList(List([1 .. Random([0 .. Q])], j -> Random([1 .. Q])))); od; if IsInt(a) then return(Automaton(T, Q, a+1, transitions, SSortedList(List([1 .. Random([1 .. Q])], j -> Random([1 .. Q]))), SSortedList(List([1 .. Q], j -> Random([1 .. Q]))))); else if jascii[Position(jascii, '@')] in a then Error("Please choose an alphabet, without the character '@'"); fi; return(Automaton(T, Q, Concatenation(a, [jascii[Position(jascii, '@')]]), transitions, SSortedList(List([1 .. Random([1 .. Q])], j -> Random([1 .. Q]))), SSortedList(List([1 .. Q], j -> Random([1 .. Q]))))); fi; fi; end); ############################################################################# ## #M String( <A> ) . . . . . . . . . . . outputs the definition of an automaton as a string ## InstallMethod( String, "Automaton to string", true, [IsAutomatonObj and IsAutomatonRep], 0, function( A ) return Concatenation("Automaton(\"", String(A!.type), "\",", String(A!.states), ",\"", AlphabetOfAutomatonAsList(A), "\",", String(A!.transitions), ",", String(A!.initial), ",", String(A!.accepting), ");;"); end); ############################################################################ ## #M Methods for the comparison operations for automata. ## InstallMethod( \=, "for two automata", # IsIdenticalObj, [ IsAutomatonObj and IsAutomatonRep, IsAutomatonObj and IsAutomatonRep, ], 0, function( x, y ) return(String(x) = String(y)); end ); InstallMethod( \<, "for two automata", # IsIdenticalObj, [ IsAutomatonObj and IsAutomatonRep, IsAutomatonObj and IsAutomatonRep, ], 0, function( x, y ) return(String(x) < String(y)); end ); #E ##