CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

| Download

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

Views: 418346
Tweet
Share
Share
############################################################################
##
#W  sgpslinks.gi                        Manuel Delgado <[email protected]>
#W                                      Jose Morais    <[email protected]>
##
#H  @(#)$Id: sgpslinks.gi,v 1.13 $
##
#Y  Copyright (C)  2004,  CMUP, Universidade do Porto, Portugal
##
##
##
#############################################################################
##
##  This file contains some links between automata and semigroups.
##
##
############################################################################
##
#F  TransitionSemigroup(aut)
##
##  Computes the transition semigroup of a deterministic automaton
##
InstallGlobalFunction(TransitionSemigroup, function(aut)
    local   g,  tr,  i;
    
    if not IsAutomaton(aut) then
        Error("the argument must be an automaton");
    fi;
    if not aut!.type = "det" then
        Error("<A> must be deterministic");
    fi;
    g := [];
    tr := NullCompletionAut(aut)!.transitions;
    for i in tr do
        g := Concatenation(g, [Transformation(i)]);
    od;
    return Semigroup( g );
end);

###########################################################################
##
#F  SyntacticSemigroupAut
##  Computes the syntactic semigroup of a deterministic automaton
## (i.e. the transition semigroup of the equivalent minimal automaton) 
##
InstallGlobalFunction(SyntacticSemigroupAut, function(aut)
    local   g,  A,  tr,  i;
    
    if not IsAutomaton(aut) then
        Error("the argument must be an automaton");
    fi;
    if not aut!.type = "det" then
        Error("<aut> must be deterministic");
    fi;
    g := [];
    A := MinimalizedAut(NullCompletionAut(aut));
    if A!.accepting = [] then
        return fail;
    fi;
    tr := A!.transitions;
    for i in tr do
        g := Concatenation(g, [Transformation(i)]);
    od;
    return Semigroup( g );
end);
###########################################################################
##
#F  SyntacticSemigroupLang(rat)
##
##  Computes the syntactic semigroup of the rational language given by the 
##  rational expression rat.
##
##
InstallGlobalFunction(SyntacticSemigroupLang, function(rat)
    return SyntacticSemigroupAut(RatExpToAut(rat));
end);

#E