SSL fsa4.g Sprache: unbekannt

Haftungsausschluß.g KontaktUnknown {[0] [0] [0]}diese Dinge liegen außhalb unserer Verantwortung

#############################################################################
##
#A  fsa4.g                  GAP library                  Derek Holt
##
##  1.3.00. created this file from GAP3 version fsa.g and started adapting
##  it to GAP4.
##
##  24/9/98 - corrected dreadful bug in DeleteStateFSA
##  This file contains those functions that deal with finite state automata.
##
## 1.5.96. - code added to deal with the new "list of words" and
## "list of integers" set-record types.
##
DeclareInfoClass("InfoFSA");
#############################################################################
#V  _RWST_                external variable - temporary name of list of strings
#V  _FSA    external variable - finite state automaton
#V  _FSA_determinize   external variable -determinized finite state automaton
#V  _FSA_min    external variable - minimized finite state automaton
#V  _FSA_not    external variable - `not' finite state automaton
#V  _FSA_star    external variable - `star' finite state automaton
#V  _FSA_reverse   external variable - `reverse' finite state automaton
#V  _FSA_exists      external variable - `exists' finite state automaton
#V  _FSA_swap_coords     external variable - `swap' finite state automaton
#V  _FSA_and        external variable - `and' finite state automaton
#V  _FSA_or        external variable - `or' finite state automaton
#V  _FSA_concat     external variable - `concat' finite state automaton
_RWST_ := [];
_FSA := rec();
_FSA_determinize := rec();
_FSA_min := rec();
_FSA_not := rec();
_FSA_star := rec();
_FSA_reverse := rec();
_FSA_exists := rec();
_FSA_swap_coords := rec();
_FSA_and := rec();
_FSA_or := rec();
_FSA_concat := rec();
_KBExtDir  :=  DirectoriesPackagePrograms("kbmag");
_KBTmpFileName := TmpName();

#############################################################################
##
#F  IsFSA(<x>) . . . . . . . test whether x is an fsa
##
##  Public function.
IsFSA := function ( x )
    return IsRecord(x) and IsBound(x.isFSA) and x.isFSA;
end;

#############################################################################
##
#F  IsInitializedFSA(<x>) . . . . . . . test whether x is an initialized fsa
##
##  Public function.
IsInitializedFSA := function ( x )
    return IsRecord(x) and IsBound(x.isInitializedFSA) and x.isInitializedFSA;
end;

#############################################################################
##
#F  ExpandFieldSR(<list>) . . expand a sparsely stored name list
##
##  ExpandFieldSR takes a sparse <list> as argument and
##  returns the corresponding dense list (which may have gaps).
##  e.g. [[1,2],[3,4]] produces output [2,,4].
##
##  Private function.
ExpandFieldSR := function ( list )
    local newlist, term;
    newlist := [];
    for term in list do
      newlist[term[1]] := term[2];
    od;
    return newlist;
end;

#############################################################################
##
#F  InitializeSR(<sr>) . . . . . . . initialize a set-record
##
##  <sr> should be a set-record conforming to the criteria.
##  The criteria are checked, various other fields are calculated and set,
##  and the existing fields are (partially) checked for validity.
##
##  Public function.
InitializeSR := function ( sr )
  local  i, j, k, s, ba, lba, nv, fld;
    if not IsBound(sr.type) or not IsBound(sr.size) then
       Error("Subfield 'type' or 'size' of set-record field is not set.");
    fi;

    if IsBound(sr.base) then
      InitializeSR(sr.base);
    fi;
    if IsBound(sr.labels) then
      InitializeSR(sr.labels);
    fi;

    # if the set record names are stored in sparse format, we
    # convert to dense format for internal use - they will still be
    # printed in sparse format.
    k := sr.type;
    if k="words" or k="identifiers" or k="strings" or
                    k="list of words" or k="list of integers" then
      if not IsBound(sr.format) or not IsBound(sr.names)
                                        or not IsList(sr.names) then
         Error(
  "Subfield 'format' or 'names' of set-record field is not set or invalid.");
      fi;
      sr.printingFormat := sr.format;
      if sr.format="sparse" then
         sr.format := "dense";
         sr.names := ExpandFieldSR(sr.names);
      fi;
    fi;

    if k="words" or k="list of words" then
      if not IsBound(sr.alphabet) or not IsList(sr.alphabet) then
         Error(
  "Subfield 'alphabet' of set-record field is not set or invalid.");
      fi;
    fi;

    if k="labeled" or k="labelled" then
      if not IsBound(sr.format)
         or not IsBound(sr.labels) or not IsRecord(sr.labels)
         or not IsBound(sr.setToLabels) or not IsList(sr.setToLabels) then
         Error(
           "Some required field for type \"labeled\"  is not set or invalid.");
      fi;
      sr.printingFormat := sr.format;
      if  sr.format="sparse" then
        sr.format := "dense";
        sr.setToLabels := ExpandFieldSR(sr.setToLabels);
      fi;
    fi;

    if k="product" then
      if not IsBound(sr.padding) or not IsBound(sr.arity)
          or not IsBound(sr.base) or not IsRecord(sr.base)  then
         Error("Some required field for type \"product\" is not set.");
      fi;
      if IsBound(sr.base.names) then
    # calculate names of set-record members
        ba := Concatenation(sr.base.names,[sr.padding]);
        lba := Length(ba);
        nv := sr.arity;
        sr.names := [];
        fld := sr.names;
        s := sr.size;
        for i in [1..s] do
          fld[i]:=[];
          k := i-1;
          for j in Reversed([1..nv]) do
            fld[i][j] := ba[k mod lba + 1];
              k := Int(k/lba);
          od;
        od;
      fi;
    fi;

end;

#############################################################################
##
#F  InitializeFSA(<fsa>) . . . . . . . initialize an fsa
##
##  <fsa> should be an fsa-record conforming to the criteria.
##  The criteria are checked, various other fields are calculated and set,
##  and the existing fields are (partially) checked for validity.
##  The entries in the flag field ("DFA", "minimized", "BFS", etc.)
##  are assumed to be valid if set.
##
##  Public function.
InitializeFSA := function ( fsa )
    local ns, ne, i, j;
# First check that the fsa has the 7 compulsory fields.
    if not IsFSA(fsa) then
       Error("Argument is not an fsa.");
    fi;
    if IsBound(fsa.isInitialized) and fsa.isInitializedFSA = true then
       Print("This fsa is already initialized.\n");
       return;
    fi;
    if not IsBound(fsa.alphabet) or not IsRecord(fsa.alphabet) then
       Error("'alphabet' field is not set, or invalid.");
    fi;
    if not IsBound(fsa.states) or not IsRecord(fsa.states) then
       Error("'states' field is not set, or invalid.");
    fi;
    if not IsBound(fsa.initial) or not IsList(fsa.initial) then
       Error("'initial' field is not set, or invalid.");
    fi;
    if not IsBound(fsa.accepting) or not IsList(fsa.accepting) then
       Error("'accepting' field is not set, or invalid.");
    fi;
    if not IsBound(fsa.table) or not IsRecord(fsa.table) then
       Error("'table' field is not set, or invalid.");
    fi;
    if not IsBound(fsa.flags) or not IsList(fsa.flags) then
       Error("'flags' field is not set, or invalid.");
    fi;

    InitializeSR(fsa.states);
    InitializeSR(fsa.alphabet);

    ns := fsa.states.size;
    ne := fsa.alphabet.size;

    fsa.initial := Set(fsa.initial);
    fsa.accepting := Set(fsa.accepting);
    fsa.flags := Set(fsa.flags);

    if not IsBound(fsa.table.format) or not IsBound(fsa.table.transitions) then
       Error("Subfield 'format' or 'transitions' of table field is not set.");
    fi;
    fsa.table.printingFormat := fsa.table.format;
    if fsa.table.format = "dense nondeterministic" then
Error("Sorry - dense nondeterministic tables not yet supported.");
    elif fsa.table.format = "dense deterministic" then
      fsa.denseDTable := fsa.table.transitions;
      if Length(fsa.denseDTable) <> ns then
        Error("Length of transition table wrong.");
      fi;
      for i in [1..ns] do
        for j in [1..ne] do
          if not IsBound(fsa.denseDTable[i][j]) then
            fsa.denseDTable[i][j] := 0;
          fi;
        od;
      od;
    elif fsa.table.format = "sparse" then
      fsa.sparseTable := fsa.table.transitions;
      if Length(fsa.sparseTable) <> ns then
        Error("Length of transition table wrong.");
      fi;
    else
      Error("Invalid transition table format.");
    fi;

    fsa.isInitializedFSA := true;
end;

#############################################################################
##
#F  FSA(alphabet) . . . . . . . make an initialized FSA with a
##  specified alphabet and a single state which is both accepting and initial
##
##  Public function.
FSA := function ( alphabet )
    local F;
    F := rec();
    F.isFSA := true;
    F.alphabet := alphabet;
    F.states := rec(type := "simple",size := 1);
    F.flags := ["DFA"];
    F.initial := [1];
    F.accepting := [1];
    F.table := rec(
      format := "dense deterministic",
      numTransitions := 0,
         transitions := [0 * [1..alphabet.size]]
    );
    InitializeFSA(F);

    return F;
end;

#############################################################################
#F  AlphabetFSA
##
##  Public function.
AlphabetFSA := fsa -> fsa.alphabet;

#############################################################################
#F  StatesFSA
##
##  Public function.
StatesFSA := fsa -> fsa.states;

#############################################################################
#F  NumberOfStatesFSA
##
##  Public function.
NumberOfStatesFSA := fsa -> fsa.states.size;

#############################################################################
#F  NumberOfLettersFSA
#F  SizeOfAlphabetFSA
##
##  Public function.
NumberOfLettersFSA := fsa -> fsa.alphabet.size;
SizeOfAlphabetFSA := fsa -> fsa.alphabet.size;

#############################################################################
##
#F  IsDeterministicFSA(<fsa>) . . . . . . . test if fsa is deterministic
##
##  Tests if the fsa <fsa> is deterministic.
##  The definition of deterministic used here is that of a partial
##  deterministic finite state automaton, rather than a total one.
##  This means, no epsilon-transtions, *at most* one initial state and
##  *at most one* transition from any state with a given label.
##  An FSA is is non-deterministic (NFA) if one of these conditions fails.
##
##  Public function.
IsDeterministicFSA := function ( fsa )
    local term, subterm, dfa_check;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if "DFA" in fsa.flags then
      return true;
    fi;
    if "NFA" in fsa.flags then
      return false;
    fi;
    if Length(fsa.initial) > 1 then
      AddSet(fsa.flags,"NFA");
      return false;
    fi;
    if IsBound(fsa.denseDTable) then
# This must imply DFA
      AddSet(fsa.flags,"DFA");
      return true;
    fi;
    for term in fsa.sparseTable do
    # sparseTable must be bound at this point
      dfa_check:=[];
      for subterm in term do
        if subterm[1]=0 or subterm[1]="epsilon" or
             IsBound(dfa_check[subterm[1]]) then
          AddSet(fsa.flags,"NFA");
          return false;
        else
          dfa_check[subterm[1]] := 1;
        fi;
      od;
    od;

    AddSet(fsa.flags,"DFA");
    return true;
end;

#############################################################################
##
#F  SparseTableToDenseDTableFSA(<fsa>) . . get DenseDTable from SparseTable
##  SparseTableToDenseDTableFSA calculates the DenseDTable of the fsa from
##  the SparseTable and  returns it.
##
##  Private function.
SparseTableToDenseDTableFSA := function ( fsa )
    local denseDTable, sparseTable, row, newrow, dt, ne, term, i;
    ne := fsa.alphabet.size;
    sparseTable := fsa.sparseTable;
    if IsBound(fsa.table.defaultTarget) then
      dt:=fsa.table.defaultTarget;
    else
      dt:=0;
    fi;
    denseDTable := [];
    for row in sparseTable do
      newrow:=[];
      for i in [1..ne] do newrow[i]:=dt; od;
      for term in row do
        if term[1]=0 or newrow[term[1]] <> dt then
          AddSet(fsa.flags,"NFA");
       Error("This fsa is nondeterministic, so cannot create DenseDTable.\n");
        fi;
        newrow[term[1]]:=term[2];
      od;
      Add(denseDTable,newrow);
    od;
    return denseDTable;
end;

#############################################################################
##
#F  DenseDTableToSparseTableFSA(<fsa>) . . get SparseTable from DenseDTable
##  DenseDTableToSparseTableFSA calculates the SparseTable of the fsa
##  from the DenseDTable and returns it.
##
##  Private function.
DenseDTableToSparseTableFSA := function ( fsa )
    local denseDTable, sparseTable, row, newrow, dt, ne, i;
    ne := fsa.alphabet.size;
    denseDTable := fsa.denseDTable;
    if IsBound(fsa.table.defaultTarget) then
      dt:=fsa.table.defaultTarget;
    else
      dt:=0;
    fi;
    sparseTable := [];
    for row in denseDTable do
      newrow:=[];
      for i in [1..ne] do
        if row[i] <> dt then
          Add(newrow,[i,row[i]]);
        fi;
      od;
      Add(sparseTable,newrow);
    od;
    return sparseTable;
end;

#############################################################################
##
#F  DenseDTableToBackTableFSA(<fsa>)  . . . . get BackTable from DenseDTable
##  DenseDTableToBackTableFSA calculates the BackTable of the fsa from the
##  DenseDTable and  returns it.
##
##  Private function.
DenseDTableToBackTableFSA := function ( fsa )
    local denseDTable, backTable, row, ne, ns, i, j;
    ne := fsa.alphabet.size;
    ns := fsa.states.size;
    denseDTable := fsa.denseDTable;
    backTable := [];
    for i in [1..ns] do
      backTable[i] := [];
    od;
    for i in [1..ns] do
      row := denseDTable[i];
      for j in [1..ne] do
        if row[j] in [1..ns] then
          Add(backTable[row[j]],[j,i]);
        fi;
      od;
    od;
    return backTable;
end;

#############################################################################
##
#F  SparseTableToBackTableFSA(<fsa>)  . . . . get BackTable from SparseTable
##  SparseTableToBackTableFSA calculates the BackTable of the fsa from
##  the SparseTable and returns it.
##  The backTable still does not include "default-target" edges.
##
##  Private function.
SparseTableToBackTableFSA := function ( fsa )
    local sparseTable, backTable, row, ne, ns, i, term;
    ne := fsa.alphabet.size;
    ns := fsa.states.size;
    sparseTable := fsa.sparseTable;
    backTable := [];
    for i in [1..ns] do
      backTable[i] := [];
    od;
    for i in [1..ns] do
      row := sparseTable[i];
      for term in row do
        if term[2] in [1..ns] then
          Add(backTable[term[2]],[term[1],i]);
        fi;
      od;
    od;
    return backTable;
end;

#############################################################################
##
#F  DenseDTableFSA(<fsa>) . . . . . . . calculates DenseDTable of dfa
##  DenseDTableFSA calculates the DenseDTable of the fsa <fsa> and returns it.
##  Public function.
DenseDTableFSA := function ( fsa )
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if not IsBound(fsa.denseDTable) then
       fsa.denseDTable := SparseTableToDenseDTableFSA(fsa);
    fi;
    return fsa.denseDTable;
end;


#############################################################################
##
#F  SparseTableFSA(<fsa>) . . . . . . . calculates DenseDTable of fsa
##  SparseTableFSA calculates the SparseTable of the fsa and returns it.
##  Public function.
SparseTableFSA := function ( fsa )
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if not IsBound(fsa.sparseTable) then
       fsa.sparseTable := DenseDTableToSparseTableFSA(fsa);
    fi;
    return fsa.sparseTable;
end;

#############################################################################
##
#F  BackTableFSA(<fsa>) . . . . . . . calculates BackTable of fsa
##  BackTableFSA calculates the BackTable of the fsa and returns it.
##  If calculated from the SparseTable, it will not include "default-target"
##  edges.
##  Public function.
BackTableFSA := function ( fsa )
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if not IsBound(fsa.backTable) then
       if IsBound(fsa.denseDTable) then
         fsa.backTable := DenseDTableToBackTableFSA(fsa);
       else
         fsa.backTable := SparseTableToBackTableFSA(fsa);
       fi;
    fi;
    return fsa.backTable;
end;

#############################################################################
##
#F  LinePrintFSA(<line> [,<filename>]) . . . . . . . print the line x
##
##  LinePrintFSA prints the line (a string) to the terminal (default)
##  or to file filename  if specified, formatting nicely.
##  It works by building up the material to be printed line by line as strings,
##  and calling LinePrintFSA to print each individual line.
##
LinePrintFSA := function ( arg )
    local line, filename;
    line := arg[1];
    if Length(arg) = 1 then filename := "";
    else filename := arg[2];
    fi; if filename = "" then Print(line,"\n");
    else AppendTo(filename,line,"\n");
    fi;
end;

#############################################################################
##
#F  WordToStringSR( <word>, <gens>, <names> )
##                                     . . . . . converts <word> to a string
##
## <word> is a word in generators <gens>.
## <names> is a list of printing strings for <gens>.
## The word is converted into a string representing the word for printing.
WordToStringSR := function ( word, gens, names )
   local string, i, l, ls, ng, g, ct, lg;
   l := Length(word);
   if l=0 then
      return "IdWord";
   fi;
   string := "";
   lg := 0; ct := 0;
   for i in [1..l] do
     g := Position(gens,Subword(word,i,i));
     if g <> lg and lg <> 0 then
        if string<>"" then string := Concatenation(string,"*"); fi;

        ng := names[lg];
        if ct > 1 then
           #Check to see if names[lg] ends "^-1"
           ls := Length(ng);
           if ls>3 and ng[ls-2]='^' and ng[ls-1]='-' and ng[ls]='1' then
             string := Concatenation(string,ng{[1..ls-1]},String(ct));
           else
             string := Concatenation(string,ng,"^",String(ct));
           fi;
        else string := Concatenation(string,ng);
        fi;
        ct := 0;
     fi;
     lg := g; ct := ct+1;
   od;
   if string<>"" then string := Concatenation(string,"*"); fi;
   ng := names[lg];
   if ct > 1 then
       #Check to see if names[lg] ends "^-1"
       ls := Length(ng);
       if ls>3 and ng[ls-2]='^' and ng[ls-1]='-' and ng[ls]='1' then
         string := Concatenation(string,ng{[1..ls-1]},String(ct));
       else
         string := Concatenation(string,ng,"^",String(ct));
       fi;
   else string := Concatenation(string,ng);
   fi;

   return string;
end;

#############################################################################
##
#F  WriteSetRecordSR(<sr> [<name>, <filename>, <offset>, <endsymbol>])
##                                  . . print the set record <sr>
##
##  WriteSetRecordSR prints the set record <sr> to the terminal (default)
##  or to file <filename> if specified, formatting nicely.
##  It works by building up the material to be printed line by line as strings,
##  and calling LinePrintFSA to print each individual line.
##  If the optional string <name> is present, printing is preceded by an
##  assignment "name:=", so that the resulting file can be read back in.
##  if the optional positive integer <offset> is present then each line
##  is preceded by <offset> spaces.
##  If the optional string <endsymbol> is present, then this is printed at
##  the end (it is likely to be ";" or ",").
##
##  Private function.
WriteSetRecordSR := function ( arg )
    local  sr, filename, name, offset, endsymbol, offstring, line, ct, first,
    pn,  wstring, i, tempfn, ids;
    sr := arg[1];
    if (sr.type="identifiers" or sr.type="words" or sr.type="list of words")
         and not IsBound(sr.printingStrings) then
    ## To find out what the printing strings should be, the only way is to
    ## output the identifiers as strings to a temporary file and read back in.
       tempfn:=TmpName();
       if sr.type="identifiers" then
         ids:=sr.names;
       else
         ids:=sr.alphabet;
       fi;
       PrintTo(tempfn,"_RWST_:=[");
       for i in [1..Length(ids)] do
         if i>1 then AppendTo(tempfn,","); fi;
         AppendTo(tempfn,"\"",ids[i],"\"");
       od;
       AppendTo(tempfn,"];\n");
       Read(tempfn);
       sr.printingStrings:=_RWST_;
       Exec(Concatenation("/bin/rm -f ",tempfn));
    fi;
    filename := "";
    name := "";
    endsymbol := "";
    offset:=0;
    if Length(arg)>=2 then
      name := arg[2];
    fi;
    if Length(arg)>=3 then
      filename := arg[3];
    fi;
    if Length(arg)>=4 then
      offset := arg[4];
    fi;
    if Length(arg)>=5 then
      endsymbol := arg[5];
    fi;
    if not IsInt(offset) or offset<=0 then
       offset := 0;
    fi;
    offstring := String("",offset);
    if name = "" then
      line := "rec (";
    else
      line := Concatenation(String(name,16+offset-4)," := rec (");
    fi;
    LinePrintFSA(line,filename);

    line := Concatenation(offstring,String("type",16),
                                                 " := ","\"",sr.type,"\"",",");
    LinePrintFSA(line,filename);
    line := Concatenation(offstring,String("size",16)," := ",String(sr.size));
    if sr.type <> "simple" then
      line := Concatenation(line,",");
    fi;
    LinePrintFSA(line,filename);
    if sr.type = "product" then
      line:=Concatenation(offstring,String("arity",16)," := ",
       String(sr.arity),",");
      LinePrintFSA(line,filename);
      line:=Concatenation(offstring,String("padding",16)," := _,");
      LinePrintFSA(line,filename);
      WriteSetRecordSR(sr.base,"base",filename,offset+4);
    elif sr.type="words" or sr.type="identifiers" or sr.type="strings"
         or sr.type="list of words" or  sr.type="list of integers" then
      if sr.type="strings" then
        pn := [];
        for i in [1..sr.size] do
           pn[i] := Concatenation("\"",sr.names[i],"\"");
        od;
      elif sr.type="words" or sr.type="identifiers" or
           sr.type="list of words" then
        pn := sr.printingStrings;
      fi;
      if sr.type="words"  or sr.type="list of words" then
        line := Concatenation(offstring,String("alphabet",16)," := [");
        ct := 1;
        while ct <= Length(sr.alphabet) do
          if ct=1 or Length(line)+Length(pn[ct]) <= 76 then
            if ct > 1 then
               line := Concatenation(line,",");
            fi;
            line := Concatenation(line,pn[ct]);
          else
            line := Concatenation(line,",");
            LinePrintFSA(line,filename);
            line := String("",21+offset);
            line := Concatenation(line,pn[ct]);
          fi;
          ct := ct+1;
        od;
        line := Concatenation(line,"],");
        LinePrintFSA(line,filename);
      fi;
      line := Concatenation(offstring,String("format",16)," := ");
      line := Concatenation(line,"\"",sr.printingFormat,"\"",",");
      LinePrintFSA(line,filename);
      line := Concatenation(offstring,String("names",16)," := [");
      if sr.printingFormat="dense" then
# recall that the names are always stored internally in dense format.
        ct := 1;
        while ct <= sr.size do
          if sr.type="words" then
            wstring := WordToStringSR(sr.names[ct],sr.alphabet,pn);
          elif sr.type="list of words" then
            wstring:="[";
            for i in [1..Length(sr.names[ct])] do
              if i>1 then
                wstring:=Concatenation(wstring,",");
              fi;
              wstring:=Concatenation(wstring,
                 WordToStringSR(sr.names[ct][i],sr.alphabet,pn) );
            od;
            wstring:=Concatenation(wstring,"]");
          elif sr.type="list of integers" then
            wstring:="[";
            for i in [1..Length(sr.names[ct])] do
              if i>1 then
                wstring:=Concatenation(wstring,",");
              fi;
              wstring:=Concatenation(wstring,String(sr.names[ct][i]));
            od;
            wstring:=Concatenation(wstring,"]");
          else wstring := pn[ct];
          fi;
          if ct=1 or Length(line)+Length(wstring) <= 76 then
            if ct > 1 then
               line := Concatenation(line,",");
            fi;
            line := Concatenation(line,wstring);
          else
            line := Concatenation(line,",");
            LinePrintFSA(line,filename);
            line := String("",21+offset);
            line := Concatenation(line,wstring);
          fi;
          ct := ct+1;
        od;
        line := Concatenation(line,"]");
        LinePrintFSA(line,filename);
      else
        ct := 1;
        first := true;
        while ct <= sr.size do
          if IsBound(sr.names[ct]) then
             if sr.type="words" then
                 wstring :=
                     WordToStringSR(sr.names[ct],sr.alphabet,pn);
             elif sr.type="list of words" then
               wstring:="[";
               for i in [1..Length(sr.names[ct])] do
                 if i>1 then
                   wstring:=Concatenation(wstring,",");
                 fi;
                 wstring:=Concatenation(wstring,
                   WordToStringSR(sr.names[ct][i],sr.alphabet,pn) );
               od;
               wstring:=Concatenation(wstring,"]");
             elif sr.type="list of integers" then
               wstring:="[";
               for i in [1..Length(sr.names[ct])] do
                 if i>1 then
                   wstring:=Concatenation(wstring,",");
                 fi;
                 wstring:=Concatenation(wstring,String(sr.names[ct][i]));
               od;
               wstring:=Concatenation(wstring,"]");
             else wstring := pn[ct];
             fi;
             if first then
               line := Concatenation
                     (line,"[",String(ct),",",wstring,"]");
               first := false;
             else
               line := Concatenation(line,",");
               LinePrintFSA(line,filename);
               line := String("",21+offset);
               line := Concatenation
                     (line,"[",String(ct),",",wstring,"]");
             fi;
          fi;
          ct := ct+1;
        od;
        LinePrintFSA(line,filename);
        line := Concatenation(String("",20+offset),"]");
        LinePrintFSA(line,filename);
      fi;
    elif sr.type = "labeled" or sr.type="labelled"  then
      WriteSetRecordSR(sr.labels,"labels",filename,offset+4,",");
      line := Concatenation(offstring,String("format",16)," := ");
      line := Concatenation(line,"\"",sr.printingFormat,"\"",",");
      LinePrintFSA(line,filename);
      line := Concatenation(offstring,String("setToLabels",16)," := [");
      if sr.printingFormat="dense" then
        ct := 1;
        while ct <= sr.size do
          if not IsBound(sr.setToLabels[ct]) then
            if ct>1 then
              line := Concatenation(line,",");
            fi;
          elif ct=1 or
           Length(line)+Length(String(sr.setToLabels[ct])) <= 76 then
            if ct > 1 then
               line := Concatenation(line,",");
            fi;
            line := Concatenation(line,String(sr.setToLabels[ct]));
          else
            line := Concatenation(line,",");
            LinePrintFSA(line,filename);
            line := String("",21+offset);
            line := Concatenation(line,String(sr.setToLabels[ct]));
          fi;
          ct := ct+1;
        od;
        line := Concatenation(line,"]");
        LinePrintFSA(line,filename);
      else
        ct := 1;
        first := true;
        while ct <= sr.size do
          if IsBound(sr.setToLabels[ct]) then
             if first then
               line := Concatenation
                     (line,"[",String(ct),",",String(sr.setToLabels[ct]),"]");
               first := false;
             else
               line := Concatenation(line,",");
               LinePrintFSA(line,filename);
               line := String("",21+offset);
               line := Concatenation
                     (line,"[",String(ct),",",String(sr.setToLabels[ct]),"]");
             fi;
          fi;
          ct := ct+1;
        od;
        LinePrintFSA(line,filename);
        line := Concatenation(String("",20+offset),"]");
        LinePrintFSA(line,filename);
      fi;
    elif sr.type <> "simple" then
       Error("Invalid type for set record.");
    fi;
    if name = "" then
      line := Concatenation(")",endsymbol);
    else
      line := String(")",16+offset-4);
      line := Concatenation(line,endsymbol);
    fi;
    LinePrintFSA(line,filename);
end;

#############################################################################
##
#F  WriteFSA(<fsa> [<name>, <filename>, <endsymbol>]) . . print the fsa "fsa"
##
##  WriteFSA prints the fsa <fsa> to the terminal (default) or to
##  file <filename> if specified, formatting nicely.
##  It works by building up the material to be printed line by line as strings,
##  and calling LinePrintFSA to print each individual line.
##  If the optional string <name> is present, printing is preceded by an
##  assignment "name:=", so that the resulting file can be read back in.
##  If the optional string <endsymbol> is present, then this is printed at
##  the end (it is likely to be ";" or ",").
##
##  Public function.
WriteFSA := function ( arg )
    local  fsa, ns, ne, filename, name, tabletype, table, endsymbol,
           line, ct, first, i, j;
    fsa := arg[1];
    filename := "";
    name := "";
    endsymbol := "";
    if Length(arg)>=2 then
      name := arg[2];
    fi;
    if Length(arg)>=3 then
      filename := arg[3];
    fi;
    if Length(arg)>=4 then
      endsymbol := arg[4];
    fi;

    if not IsInitializedFSA(fsa) then
      InitializeFSA(fsa);
    fi;
    ns := fsa.states.size;
    ne := fsa.alphabet.size;
    if filename = "" and name = "" then
      Print("rec (\n");
    elif filename = "" and name <> "" then
      Print(name," := \nrec (\n");
    elif filename <> "" and name = "" then
      PrintTo(filename,"rec (\n");
    else
      PrintTo(filename,name," := \nrec (\n");
    fi;

    line := String("isFSA",16);
    line := Concatenation(line," := true,");
    LinePrintFSA(line,filename);

    WriteSetRecordSR(fsa.alphabet,"alphabet",filename,4,",");
    WriteSetRecordSR(fsa.states,"states",filename,4,",");

    line := String("flags",16);
    line := Concatenation(line," := [");
    first := true;
    for i in fsa.flags do
      if not first then
        line := Concatenation(line,",");
      fi;
      first := false;
      line := Concatenation(line,"\"",i,"\"");
    od;
    line := Concatenation(line,"],");
    LinePrintFSA(line,filename);

    line := String("initial",16);
    line := Concatenation(line," := [");
    ct := 1;
    while ct<= Length(fsa.initial) do
      if ct=1 or Length(line)+Length(String(fsa.initial[ct])) <= 76 then
        if ct > 1 then
           line := Concatenation(line,",");
        fi;
        line := Concatenation(line,String(fsa.initial[ct]));
      else
        line := Concatenation(line,",");
        LinePrintFSA(line,filename);
        line := String("",21);
        line := Concatenation(line,String(fsa.initial[ct]));
      fi;
      ct := ct+1;
    od;
    line := Concatenation(line,"],");
    LinePrintFSA(line,filename);

    line := String("accepting",16);
    line := Concatenation(line," := [");
    ct := 1;
    if ns>1 and fsa.accepting=[1..ns] then
       line := Concatenation(line,"1..",String(ns));
    else
      while ct<= Length(fsa.accepting) do
        if ct=1 or Length(line)+Length(String(fsa.accepting[ct])) <= 76 then
          if ct > 1 then
             line := Concatenation(line,",");
          fi;
          line := Concatenation(line,String(fsa.accepting[ct]));
        else
          line := Concatenation(line,",");
          LinePrintFSA(line,filename);
          line := String("",21);
          line := Concatenation(line,String(fsa.accepting[ct]));
        fi;
        ct := ct+1;
      od;
    fi;
    line := Concatenation(line,"],");
    LinePrintFSA(line,filename);

    tabletype := fsa.table.printingFormat;

    if tabletype="dense deterministic"  then
      if IsDeterministicFSA(fsa) = false then
        fsa.table.printingFormat := "sparse";
        tabletype := fsa.table.printingFormat;
      elif not IsBound(fsa.denseDTable) then
        DenseDTableFSA(fsa);
      fi;
    fi;
    if tabletype="sparse" and not IsBound(fsa.sparseTable) then
      SparseTableFSA(fsa);
    fi;
    if tabletype="dense deterministic" then
      table := fsa.denseDTable;
      fsa.table.format := "dense deterministic";
# Calculate number of nontrivial transitions
      ct := 0;
      for i in [1..ns] do
        for j in [1..ne] do
          if table[i][j] <> 0 then
            ct := ct+1;
          fi;
        od;
      od;
    else
      table := fsa.sparseTable;
      fsa.table.format := "sparse";
# Calculate number of nontrivial transitions
      ct := 0;
      for i in [1..ns] do
        ct := ct + Length(table[i]);
      od;
    fi;
    fsa.table.numTransitions := ct;

    line := Concatenation(String("table",16)," := rec(");
    LinePrintFSA(line,filename);
    line := Concatenation(String("format",20),
                                      " := ","\"",fsa.table.format,"\"",",");
    LinePrintFSA(line,filename);
    line := Concatenation(String("numTransitions",20)," := ",
                           String(fsa.table.numTransitions),",");
    LinePrintFSA(line,filename);
    if tabletype = "sparse" and IsBound(fsa.table.defaultTarget) then
      line := Concatenation(line,String("defaultTarget",20)," := ");
      line := Concatenation(line,String(fsa.table.defaultTarget),",");
      LinePrintFSA(line,filename);
    fi;
    line := Concatenation(String("transitions",20)," := [");
    if ns=0 then
      LinePrintFSA(line,filename);
    fi;
    first := true;
    for i in [1..ns] do
      if first then
        line := Concatenation(line,"[");
        first := false;
      else
        line := Concatenation(String("",25),"[");
      fi;
      ct := 1;
      while ct<= Length(table[i]) do
        if ct=1 or Length(line)+Length(String(table[i][ct])) <= 76 then
          if ct > 1 then
             line := Concatenation(line,",");
          fi;
          line := Concatenation(line,String(table[i][ct]));
        else
          line := Concatenation(line,",");
          LinePrintFSA(line,filename);
          line := String("",25);
          line := Concatenation(line,String(table[i][ct]));
        fi;
        ct := ct+1;
      od;
      line := Concatenation(line,"]");
      if i<ns then
        line := Concatenation(line,",");
      fi;
      LinePrintFSA(line,filename);
    od;
    line := Concatenation(String("",20),"]");
    LinePrintFSA(line,filename);
    line := Concatenation(String("",16),")");
    LinePrintFSA(line,filename);

    line := Concatenation(")",endsymbol);
    LinePrintFSA(line,filename);
end;

#############################################################################
##
#F  ElementNumberSR(<sr>, <el>)  . . . get number of set-record element.
##
##  <sr> should be a set-record. <el> should either be a positive integer
##  representing an element of <sr> or a name for such an element.
##  In either case, the number of the element is returned.
##  False is returned if <el> is invalid.
##
##  Private function.
ElementNumberSR := function ( sr, el )
  local IdWord;
  if IsAssocWordWithOne(el) then
    IdWord := el^0;
  else IdWord := false;
  fi;
  if IsInt(el) then
    if el>sr.size+1 then
      return false;
    else
      return el;
    fi;
  elif el=IdWord then
    return sr.size+1;
  elif IsBound(sr.names) then
    return Position(sr.names,el);
  else
    return false;
  fi;
end;

#############################################################################
##
#F  TargetDFA(<fsa>,<e>,<s>) . . . . . . . target of edge in a dfa
##  TargetDFA calculates  and returns the target of the edge in the dfa <fsa>
##  with edge <e> and source-state <s>.
##  0 is returned if there is no edge.
##  <e> can either be the number of an edge or an edge-name.
##  <s> can either be the number of a state or a state-name.
##  The returned value has same type as <s> (or 0).
##  Public function.
TargetDFA := function ( fsa,e,s )
    local tname, term, row, ns, t, ng;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsDeterministicFSA(fsa)=false  then
       Error("First argument is not a dfa.");
    fi;
    if IsList(e) then
      ng := fsa.alphabet.base.size;
      e := (ElementNumberSR(fsa.alphabet.base,e[1])-1) * (ng+1) +
       ElementNumberSR(fsa.alphabet.base,e[2]);
    else
      e := ElementNumberSR(fsa.alphabet,e);
    fi;
    if e=false then
      Error("Second argument is not a valid edge number or label.");
    fi;
    tname := not IsInt(s);
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Third argument is not a valid state number or name.");
    fi;

    ns := fsa.states.size;
    if IsBound(fsa.denseDTable) then
      t := fsa.denseDTable[s][e];
      if t=0 then
        return 0;
      fi;
      if tname then
        return  fsa.states.names[t];
      fi;
      return t;
    fi;

    row := fsa.sparseTable[s];
    for term in row do
      if term[1]=e then
        t := term[2];
        if tname then
          if t=0 then
            return 0;
          fi;
          return fsa.states.names[t];
        fi;
        return t;
      fi;
    od;
    if IsBound(fsa.table.defaultTarget) then
      t := fsa.table.defaultTarget;
    else
      return 0;
    fi;
    if tname then
      if t=0 then
        return 0;
      fi;
      return fsa.states.names[t];
    fi;
    return t;

end;

#############################################################################
##
#F  TargetsFSA(<fsa>,<e>,<s>) . . . . . . . targets of edge
##  TargetsFSA calculates the targets of the edges in the fsa <fsa>
##  with edge <e> and source-state <s>.
##  The result is returned as a list of targets.
##  <l> can either be the number of an edge-label or an edge-label-name.
##  <s> can either be the number of a state or a state-name.
##  The members of the returned list have same type as <s>.
##  Public function.
TargetsFSA := function ( fsa,e,s )
    local tname, term, targets, row, ns, t, ng;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsList(e) then
      ng := fsa.alphabet.base.size;
      e := (ElementNumberSR(fsa.alphabet.base,e[1])-1) * (ng+1) +
       ElementNumberSR(fsa.alphabet.base,e[2]);
    else
      e := ElementNumberSR(fsa.alphabet,e);
    fi;
    if e=false then
      Error("Second argument is not a valid edge number or label.");
    fi;
    tname := not IsInt(s);
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Third argument is not a valid state number or name.");
    fi;

    ns := fsa.states.size;
    if IsBound(fsa.denseDTable) then
      if e=0 then
         return [];
      fi;
      t := fsa.denseDTable[s][e];
      if t=0 then
        return [];
      fi;
      if tname then
        return [ fsa.states.names[t] ];
      fi;
      return [ t ];
    fi;

    row := fsa.sparseTable[s];
    targets := [];
    for term in row do
      if term[1]=e then
        if tname then
          if term[2]>0 and term[2]<=ns then
            Add(targets,fsa.states.names[term[2]]);
          fi;
        else
          Add(targets,term[2]);
        fi;
      fi;
    od;
    if targets=[] and IsBound(fsa.table.defaultTarget) then
      if tname then
        Add(targets,fsa.states.names[fsa.table.defaultTarget]);
      else
        Add(targets,fsa.table.defaultTarget);
      fi;
    fi;
    return targets;

end;

#############################################################################
##
#F  SourcesFSA(<fsa>,<e>,<s>) . . . . . . . sources of edge
##  SourcesFSA calculates the sources of the edges in the fsa <fsa>
##  with edge <e> and source-state <s>.
##  The result is returned as a list of sources.
##  <l> can either be the number of an edge-label or an edge-label-name.
##  <s> can either be the number of a state or a state-name.
##  The members of the returned list have same type as <s>.
##  Public function.
SourcesFSA := function ( fsa,e,s )
    local tname, term, sources, row, ns, i, none, ng;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsList(e) then
      ng := fsa.alphabet.base.size;
      e := (ElementNumberSR(fsa.alphabet.base,e[1])-1) * (ng+1) +
       ElementNumberSR(fsa.alphabet.base,e[2]);
    else
      e := ElementNumberSR(fsa.alphabet,e);
    fi;
    if e=false then
      Error("Second argument is not a valid edge number or label.");
    fi;
    tname := not IsInt(s);
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Third argument is not a valid state number or name.");
    fi;

  #We need the backTable for this.
    BackTableFSA(fsa);
    row := fsa.backTable[s];
    sources := [];
    ns := fsa.states.size;
    for term in row do
      if term[1]=e then
        if tname then
          if term[2]>0 and term[2]<=ns then
            Add(sources,fsa.states.names[term[2]]);
          fi;
        else
          Add(sources,term[2]);
        fi;
      fi;
    od;
    if IsBound(fsa.table.defaultTarget) and fsa.table.defaultTarget=s and
          IsBound(fsa.sparseTable) then
    # there may be some "default-target" edges.
       for i in [1..ns] do
         row := fsa.sparseTable[i];
         none := true;
         for term in row do
           if term[1]=e then none:=false; fi;
         od;
         if none then
           Add(sources,i);
         fi;
       od;
       sources := Set(sources);
    fi;
    return sources;
end;

#############################################################################
##
#F  IsAcceptedWordDFA(<fsa>,<w>) . . . . . . . tests if word accepted by fsa
##  IsAcceptedWordDFA tests whether the word <w> is accepted by the
##  deterministic fsa <fsa>, and returns true or false.
##  <w> can either be a list of labels or a list of label numbers,
##  or a word in the labels for <fsa>.
##  (In the last case, the labels must be abstract generators.)
##  For an n-variable fsa, it can also be a list of n words (which will
##  be padded out at the end by the padding symbol).
##  Public function.
IsAcceptedWordDFA := function ( fsa,w )
    local state, label, len, iw, inw, nl, ps, ns, nv, i, pos, dead;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsDeterministicFSA(fsa)=false then
       Error("Argument is not a dfa.");
    fi;
    if fsa.initial=[] then
      return false;
    fi;
    ns := fsa.states.size;
    state := fsa.initial[1];
    iw := IsWord(w);
    inw := false;
    if not iw and not IsList(w) then
      Error("Second argument must be a word or a list.");
    fi;
    if IsBound(fsa.alphabet.arity) and IsList(w) and IsWord(w[1]) then
      if not IsBound(fsa.alphabet.base.names) then
        Error("Can only span n-tuple of words if base-alphabet has names.");
      fi;
      if not IsBound(fsa.alphabet.padding) then
        Error("Can only span n-tuple of words if there is a padding symbol.");
      fi;
      ps := fsa.alphabet.padding;
      inw := true;
      nv := fsa.alphabet.arity;
      nl := [];
      for i in [1..nv] do
        nl[i] := Length(w[i]);
      od;
      len := Maximum(nl);
    elif iw then
      len := Length(w);
    else
      len := Length(w);
    fi;
    dead := false;
    pos := 1;
    while not dead and pos <= len do
      if inw then
         label := [];
         for i in [1..nv] do
           if pos <= nl[i] then
             label[i] := Subword(w[i],pos,pos);
           else
             label[i] := ps;
           fi;
         od;
      elif iw then
        label := Subword(w,pos,pos);
      else
        label := w[pos];
      fi;
      state := TargetDFA(fsa,label,state);
      if not state in [1..ns] then
        dead:=true;
      fi;
      pos := pos+1;
    od;
    if dead then
      return false;
    fi;
    return state in fsa.accepting;
end;

#############################################################################
##
#F  WordTargetDFA(<fsa>,<w>) . . . . . . . target of word under DFA
##  WordTargetDFA finds the target state when the word <w> is read by
##  the deterministic fsa <fsa>, and returns this state or 0.
##  <w> can either be a list of labels or a list of label numbers,
##  or a word in the labels for <fsa>.
##  (In the last case, the labels must be abstract generators.)
##  For an n-variable fsa, it can also be a list of n words (which will
##  be padded out at the end by the padding symbol).
##  Public function.
WordTargetDFA := function ( fsa,w )
    local state, label, len, iw, inw, nl, ps, ns, nv, i, pos, dead;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsDeterministicFSA(fsa)=false then
       Error("Argument is not a dfa.");
    fi;
    if fsa.initial=[] then
      return 0;
    fi;
    ns := fsa.states.size;
    state := fsa.initial[1];
    iw := IsWord(w);
    inw := false;
    if not iw and not IsList(w) then
      Error("Second argument must be a word or a list.");
    fi;
    if IsBound(fsa.alphabet.arity) and IsList(w) and IsWord(w[1]) then
      if not IsBound(fsa.alphabet.base.names) then
        Error("Can only span n-tuple of words if base-alphabet has names.");
      fi;
      if not IsBound(fsa.alphabet.padding) then
        Error("Can only span n-tuple of words if there is a padding symbol.");
      fi;
      ps := fsa.alphabet.padding;
      inw := true;
      nv := fsa.alphabet.arity;
      nl := [];
      for i in [1..nv] do
        nl[i] := Length(w[i]);
      od;
      len := Maximum(nl);
    elif iw then
      len := Length(w);
    else
      len := Length(w);
    fi;
    dead := false;
    pos := 1;
    while not dead and pos <= len do
      if inw then
         label := [];
         for i in [1..nv] do
           if pos <= nl[i] then
             label[i] := Subword(w[i],pos,pos);
           else
             label[i] := ps;
           fi;
         od;
      elif iw then
        label := Subword(w,pos,pos);
      else
        label := w[pos];
      fi;
      state := TargetDFA(fsa,label,state);
      if not state in [1..ns] then
        dead:=true;
      fi;
      pos := pos+1;
    od;
    if dead then
      return 0;
    fi;
    return state;
end;

#############################################################################
##
#F  AddStateFSA(<fsa>[,<name>]) . . . . . . . adds state to an fsa
##  AddStateFSA adds a state to the end of the statelist of the fsa <fsa>.
##  It has the optional name or label <name> (but if the state-type is
##  "named", then the name must be supplied).
##  Public function.
AddStateFSA := function ( arg )
    local fsa, name, ns, new, i, dt;
    fsa := arg[1];
    if fsa.states.type = "product" then
      Error("Cannot alter a product-type state-list");
    fi;
    if Length(arg)=1 and IsBound(fsa.states.names) then
       Error("You must supply a name for the new state.");
    fi;
    name:="";
    if Length(arg)=2 then
      name:=arg[2];
    fi;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    fsa.states.size := fsa.states.size+1;
    ns := fsa.states.size;
    if name<>"" and IsBound(fsa.states.names) then
        fsa.states.names[ns] := name;
    fi;
    if IsBound(fsa.denseDTable) then
      if IsBound(fsa.table.defaultTarget) then
        dt := fsa.table.defaultTarget;
      else
        dt := 0;
      fi;
      new:=[];
      for i in [1..fsa.alphabet.size] do new[i]:=dt; od;
      Add(fsa.denseDTable,new);
    fi;
    if IsBound(fsa.sparseTable) then
      new:=[];
      Add(fsa.sparseTable,new);
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"minimized");
    RemoveSet(fsa.flags,"trim");
    RemoveSet(fsa.flags,"accessible");
end;

#############################################################################
##
#F  DeleteListFSA(<l>,<n>) . . . . . . . delete element from list
##  DeleteListFSA deletes the <n>-th element from list <l>, and closes
##  up. Used for deleting state from an fsa.
##
DeleteListFSA := function(l,n)
    local i, len;
    len := Length(l);
    for i in [n..len] do
      if IsBound(l[i+1]) then
        l[i]:=l[i+1];
      else
        Unbind(l[i]);
      fi;
    od;
end;

#############################################################################
##
#F  DeleteStateFSA(<fsa>) . . . . . . . delete state from an fsa
##  DeleteStateFSA deletes the final state of the fsa <fsa>.
##  All edges to and from that state are deleted.
##  To delete a state other than the final, first call PermuteStatesFSA
##  Public function.
DeleteStateFSA := function ( fsa )
    local  ns, ng, row, i, j;
    if fsa.states.type = "product" then
      Error("Cannot alter a product-type state-list");
    fi;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    ns := fsa.states.size;
    ng := fsa.alphabet.size;
    fsa.states.size:=ns-1;
    if IsBound(fsa.states.names) then
      Unbind(fsa.states.names[ns]);
    fi;
    if IsBound(fsa.states.setToLabels) then
      Unbind(fsa.states.setToLabels[ns]);
    fi;
    j := Position(fsa.initial,ns);
    if j <> fail then
      DeleteListFSA(fsa.initial,j);
    fi;
    j := Position(fsa.accepting,ns);
    if j <> fail then
      DeleteListFSA(fsa.accepting,j);
    fi;
    if IsBound(fsa.table.defaultTarget) and fsa.table.defaultTarget=ns then
      Unbind(fsa.table.defaultTarget);
    fi;
    if IsBound(fsa.denseDTable) then
      for i in [1..ns-1] do
        row:=fsa.denseDTable[i];
        for j in [1..ng] do
          if row[j]=ns then
            row[j]:=0;
          fi;
        od;
      od;
      DeleteListFSA(fsa.denseDTable,ns);
    fi;
    if IsBound(fsa.sparseTable) then
      for i in [1..ns-1] do
        row:=fsa.sparseTable[i];
        j := 1;
        while j <= Length(row) do
          if row[j][2]=ns then
            DeleteListFSA(row,j);
            j:=j-1;
          fi;
          j:=j+1;
        od;
      od;
      DeleteListFSA(fsa.sparseTable,ns);
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"NFA");
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
    RemoveSet(fsa.flags,"trim");
    RemoveSet(fsa.flags,"accessible");
end;

#############################################################################
##
#F  PermuteStatesFSA(<fsa>,p) . . . . . . . permute states of an fsa
##  PermuteStatesFSA permutes the states of the fsa <fsa>.
##  <p> should be a permutation of the state numbers.
##  What was state n is renumbered state n^p.
##  Public function.
PermuteStatesFSA := function ( fsa,p )
    local  ns, term, row, i, j, new, ne;
    if fsa.states.type = "product" then
      Error("Cannot alter a product-type state-list");
    fi;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    ns := fsa.states.size;
    ne := fsa.alphabet.size;
    if p = () then
      return;
    fi;
    if not IsPerm(p) or LargestMovedPointPerm(p)>ns then
      Error("Second argument is invalid.");
    fi;
    if IsBound(fsa.states.names) then
      new := [];
      for i in [1..ns] do
         new[i^p]:=fsa.states.names[i];
      od;
      fsa.states.names := new;
    fi;
    if IsBound(fsa.states.setToLabels) then
      new := [];
      for i in [1..ns] do
         if IsBound(fsa.states.setToLabels[i]) then
           new[i^p]:=fsa.states.setToLabels[i];
         fi;
      od;
      fsa.states.setToLabels := new;
    fi;
    for i in [1..Length(fsa.initial)] do
       fsa.initial[i]:=fsa.initial[i]^p;
    od;
    fsa.initial := Set(fsa.initial);
    for i in [1..Length(fsa.accepting)] do
       fsa.accepting[i]:=fsa.accepting[i]^p;
    od;
    fsa.accepting := Set(fsa.accepting);
    if IsBound(fsa.table.defaultTarget) and fsa.table.defaultTarget>0 then
      fsa.table.defaultTarget := fsa.table.defaultTarget^p;
    fi;
    if IsBound(fsa.denseDTable) then
      new := [];
      for i in [1..ns] do
        row := fsa.denseDTable[i];
        new[i^p] := row;
        for j in [1..ne] do
          if row[j]>0 then
            row[j] := row[j]^p;
          fi;
        od;
      od;
      fsa.denseDTable := new;
    fi;
    if IsBound(fsa.sparseTable) then
      new := [];
      for i in [1..ns] do
        row := fsa.sparseTable[i];
        new[i^p] := row;
        for term in row do
          if term[2]>0 then
            term[2] := term[2]^p;
          fi;
        od;
      od;
      fsa.sparseTable := new;
    fi;
    if fsa.table.format = "dense deterministic" then
      fsa.table.transitions := fsa.denseDTable;
    else
      fsa.table.transitions := fsa.sparseTable;
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"BFS");
end;

#############################################################################
##
#F  AddLetterFSA(<fsa>[,<name>]) . . . . . . . adds letter to alphabet of fsa
##  AddLetterFSA adds an extra symbol to the alphabet of the fsa <fsa>.
##  It has the optional name or label <name> (but if the alphabet-type is
##  a named type, then the name must be supplied).
##  Public function.
AddLetterFSA := function ( arg )
    local  fsa, name,  ne, new, term;
    fsa := arg[1];
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if fsa.alphabet.type = "product" then
      Error("Cannot alter a product-type alphabet");
    fi;
    if Length(arg)=1 and IsBound(fsa.alphabet.names) then
       Error("You must supply a name for the new state.");
    fi;
    name := "";
    if Length(arg)=2 then
      name := arg[2];
    fi;
    if not IsInitializedFSA(fsa) then
       Error("First argument is not an initialized fsa.");
    fi;
    fsa.alphabet.size := fsa.alphabet.size+1;
    ne := fsa.alphabet.size;
    if name<>""  and  IsBound(fsa.alphabet.names) then
        fsa.alphabet.names[ne] := name;
    fi;
    if IsBound(fsa.denseDTable) then
      for term in fsa.denseDTable do
        if IsBound(fsa.table.defaultTarget) then
          Add(term,fsa.table.defaultTarget);
        else
          Add(term,0);
        fi;
      od;
    fi;
end;

#############################################################################
##
#F  DeleteLetterFSA(<fsa>) . . . . . . . deletes alphabet letter from an fsa
##  DeleteLetterFSA deletes the final alphabet label from the fsa <fsa>.
##  All edges with that label are deleted.
##  To delete an edge-label other than the final, first call
##  PermuteLettersFSA
##  Public function.
DeleteLetterFSA := function ( fsa )
    local  ns, ne, term, row, i, j;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if fsa.alphabet.type = "product" then
      Error("Cannot alter a product-type alphabet");
    fi;
    ns := fsa.states.size;
    ne := fsa.alphabet.size;
    fsa.alphabet.size := ne-1;
    if IsBound(fsa.alphabet.names) then
      Unbind(fsa.alphabet.names[ne]);
    fi;
    if IsBound(fsa.alphabet.setToLabels) then
      Unbind(fsa.alphabet.setToLabels[ne]);
    fi;
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
    if IsBound(fsa.denseDTable) then
      for row in fsa.denseDTable do
        DeleteListFSA(row,ne);
      od;
    fi;
    if IsBound(fsa.sparseTable) then
      for row in fsa.sparseTable do
        j := 1;
        while j <= Length(row) do
          if row[j][1]=ne then
            DeleteListFSA(row,j);
          fi;
          j:=j+1;
        od;
      od;
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"NFA");
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
    RemoveSet(fsa.flags,"trim");
    RemoveSet(fsa.flags,"accessible");
end;

#############################################################################
##
#F  PermuteLettersFSA(<fsa>,p) . . . . . . . permute alphabet labels of an fsa
##  PermuteLettersFSA permutes the alphabet labels of the fsa <fsa>.
##  <p> should be a permutation of the alphabet labels numbers.
##  What was edge-label n is renumbered alphabet label n^p.
##  Public function.
PermuteLettersFSA := function ( fsa,p )
    local  ns, ne, term, row, i, j, new;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if fsa.alphabet.type = "product" then
      Error("Cannot alter a product-type alphabet");
    fi;
    ns := fsa.states.size;
    ne := fsa.alphabet.size;
    if not IsPerm(p) or LargestMovedPointPerm(p)>ne then
      Error("Second argument is invalid.");
    fi;
    if IsBound(fsa.alphabet.names) then
      new := [];
      for i in [1..ne] do
        new[i^p]:=fsa.alphabet.names[i];
      od;
      fsa.alphabet.names := new;
    fi;
    if IsBound(fsa.alphabet.setToLabels) then
      new := [];
      for i in [1..ne] do
         if IsBound(fsa.alphabet.setToLabels[i]) then
           new[i^p]:=fsa.alphabet.setToLabels[i];
         fi;
      od;
      fsa.alphabet.setToLabels := new;
    fi;
    if IsBound(fsa.denseDTable) then
      for i in [1..ns] do
        row := fsa.denseDTable[i];
        new := [];
        for j in [1..ne] do
          new[j^p] := row[j];
        od;
        fsa.denseDTable[i] := new;
      od;
    fi;
    if IsBound(fsa.sparseTable) then
      new := [];
      for i in [1..ns] do
        row := fsa.sparseTable[i];
        for term in row do
          if term[1]>0 then
            term[1] := term[1]^p;
          fi;
        od;
      od;
    fi;
    if fsa.table.format = "dense deterministic" then
      fsa.table.transitions := fsa.denseDTable;
    else
      fsa.table.transitions := fsa.sparseTable;
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"BFS");
end;

#############################################################################
#F  AddEdgeFSA(<fsa>,<e>,<s>,<t>) . . . . . . . adds edge to an fsa
##  AddEdge adds an edge with source <s>, label <e> and target <t>
##  to the fsa <fsa> (if there isn't one already.
##  <s> and <t> can be either numbers or names of states,
##  and <e> a number or name of an edge-label.
##  Public function.
AddEdgeFSA := function ( fsa, e, s, t )
    local row, term, ng;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsList(e) then
      ng := fsa.alphabet.base.size;
      e := (ElementNumberSR(fsa.alphabet,e[1])-1) * (ng+1) +
       ElementNumberSR(fsa.alphabet,e[2]);
    else
      e := ElementNumberSR(fsa.alphabet,e);
    fi;
    if e=false then
      Error("Second argument is not a valid edge number or label.");
    fi;
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Third argument is not a valid state number or name.");
    fi;
    t := ElementNumberSR(fsa.states,t);
    if t=false then
       Error("Fourth argument is not a valid state number or name.");
    fi;
    if e=0 or (IsBound(fsa.denseDTable) and fsa.denseDTable[s][e]>0 and
       fsa.denseDTable[s][e]<=fsa.states.size and
       fsa.denseDTable[s][e] <> t) then
    # makes non-deterministic.
      Print("Warning: gone non-deterministic!\n");
      SparseTableFSA(fsa);
      fsa.table.format := "sparse";
      fsa.table.transitions := fsa.sparseTable;
      Unbind(fsa.denseDTable);
      RemoveSet(fsa.flags,"DFA");
      AddSet(fsa.flags,"NFA");
    fi;
    if IsBound(fsa.denseDTable) then
      fsa.denseDTable[s][e] := t;
    fi;
    if IsBound(fsa.sparseTable) then
      row := fsa.sparseTable[s];
      for term in row do
        if term[1]=e and term[2]>0 and term[2]<=fsa.states.size
            and term[2] <> t then
          #makes non-deterministic
          RemoveSet(fsa.flags,"DFA");
          AddSet(fsa.flags,"NFA");
          fsa.table.format := "sparse";
        fi;
      od;
      Add(row,[e,t]);
      fsa.sparseTable[s]:=Set(row);
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
end;

#############################################################################
##
#F  DeleteEdgeFSA(<fsa>,<e>,<s>,<t>) . . . . . . . deletes edge from an fsa
##  DeleteEdgeFSA deletes an edge with source <s>, label <e> and target <t>
##  from the fsa <fsa> (if there is one).
##  <s> and <t> can be either numbers or names of states (but both the same),
##  and <e> a number or name of an edge-label.
##  Public function.
DeleteEdgeFSA := function ( fsa, e, s, t )
    local ng, row, term, subterm,  j, dfa_check;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if IsList(e) then
      ng := fsa.alphabet.base.size;
      e := (ElementNumberSR(fsa.alphabet,e[1])-1) * (ng+1) +
       ElementNumberSR(fsa.alphabet,e[2]);
    else
      e := ElementNumberSR(fsa.alphabet,e);
    fi;
    if e=false then
      Error("Second argument is not a valid edge number or label.");
    fi;
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Third argument is not a valid state number or name.");
    fi;
    t := ElementNumberSR(fsa.states,t);
    if t=false then
       Error("Fourth argument is not a valid state number or name.");
    fi;
    if IsBound(fsa.denseDTable) and fsa.denseDTable[s][e] = t then
      fsa.denseDTable[s][e]:=0;
    fi;
    if IsBound(fsa.sparseTable) then
      row := fsa.sparseTable[s];
      j := 1;
      while j <= Length(row) do
        term := row[j];
        if term[1]=e and term[2] = t then
          DeleteListFSA(row,j);
        fi;
        j := j+1;
      od;
    fi;
    Unbind(fsa.backTable);
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
    RemoveSet(fsa.flags,"NFA");
    # may have gone deterministic.
    RemoveSet(fsa.flags,"accessible");
    RemoveSet(fsa.flags,"trim");
end;

#############################################################################
##
#F  AcceptingStatesFSA(<fsa>) . . . the accepting states of <fsa>
##
AcceptingStatesFSA := function(fsa)
  return fsa.accepting;
end;

#############################################################################
##
#F  SetAcceptingFSA(<fsa>, <s>, <flag>) . . . set category of state <s>
##
##  s should be a number or name of a state in fsa <fsa>. This state
##  is made into an accepting state or not according to whether
##  <flag> is true or false.
##
##  Public function
SetAcceptingFSA := function(fsa, s, flag)
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Second argument is not a valid state number or name.");
    fi;
    if flag = true then
      AddSet(fsa.accepting,s);
    else
      RemoveSet(fsa.accepting,s);
    fi;
    RemoveSet(fsa.flags,"trim");
    RemoveSet(fsa.flags,"minimized");
end;

#############################################################################
##
#F  InitialStatesFSA(<fsa>) . . . the initial states of <fsa>
##
InitialStatesFSA := function(fsa)
  return fsa.initial;
end;

#############################################################################
##
#F  SetInitialFSA(<fsa>, <s>, <flag>) . . . set initiality of state <s>
##
##  s should be a number or name of a state in fsa <fsa>. This state
##  is made into an initial state or not according to whether
##  <flag> is true or false.
##
##  Public function
SetInitialFSA := function(fsa, s, flag)
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    s := ElementNumberSR(fsa.states,s);
    if s=false then
       Error("Second argument is not a valid state number or name.");
    fi;
    if flag = true then
      AddSet(fsa.initial,s);
    else
      RemoveSet(fsa.initial,s);
    fi;
    RemoveSet(fsa.flags,"trim");
    RemoveSet(fsa.flags,"accessible");
    RemoveSet(fsa.flags,"BFS");
    RemoveSet(fsa.flags,"minimized");
    if Length(fsa.initial) > 1 then
      RemoveSet(fsa.flags,"DFA");
    else
      RemoveSet(fsa.flags,"NFA");
    fi;
end;

#############################################################################
##
#F  IsAccessibleFSA(<fsa>) . . . . . . . test whether fsa is a accessible fsa
##
## An accessible FSA is one in which there is a word in the language
## leading to every state.
## The string "accessible" is inserted in the list of flags when it is known
## to be accessible.
## Note that "trim" implies "accessible".
##
## Public function.
IsAccessibleFSA := function ( fsa )
    local ns, ne, ct, i, j, got, s, x, t;
    if not IsInitializedFSA(fsa) then
       InitializeFSA(fsa);
    fi;
    if "accessible" in fsa.flags or "trim" in fsa.flags then
      return true;
    fi;
    ns := fsa.states.size;
    ne := fsa.alphabet.size;
# Find all accessible states i.e. states accessible from an initial state.
    got := ShallowCopy(fsa.initial);
    ct := Length(got);
    i := 1;
    while i <= ct do
      s := got[i];
      for j in [0..ne] do
        x := TargetsFSA(fsa,j,s);
        for t in x do
          if t>0 and not t in got then
            ct := ct+1;
            got[ct] := t;
          fi;
        od;
      od;
      i := i+1;
    od;
    if ct <> ns then
# there are some inaccessible states, so fsa is not accessible.
      return false;
    fi;

    AddSet(fsa.flags,"accessible");
--> --------------------

--> maximum size reached

--> --------------------

SSL fsa4.g Sprache: unbekannt

[ Verzeichnis aufwärts0.132unsichere Verbindung ]