Quelle rat-func.gi Sprache: unbekannt

#############################################################################
##
#W  rat-func.gi                         Manuel Delgado <mdelgado@fc.up.pt>
##                                      Jose Morais <josejoao@fc.up.pt>
##
##  This file contains functions that perform tests on automata
##
##
#Y  Copyright (C)  2004,  CMUP, Universidade do Porto, Portugal
##

#############################################################################
##
#F  CopyRatExp(r)
##
##  Returns a new rational expression, which is a copy
##  of the argument.
##
InstallGlobalFunction(CopyRatExp, function(r)
    local   l,  r2,  r1;

    if not IsRatExpOnnLettersObj(r) then
        Error("The argument must be a rational expression");
    fi;
    l := [];
    if r!.op = [] then
        l := ShallowCopy(r!.list_exp);
    elif not r!.op = "star" then
        for r2 in r!.list_exp do
            Add(l, CopyRatExp(r2));
        od;
    else
        l := CopyRatExp(r!.list_exp);
    fi;
    r1 := RatExpOnnLetters(FamilyObj(r)!.alphabet2, ShallowCopy(r!.op), l);
    return(r1);
end);

#############################################################################
#F  IsEmptyLang(<L>)
##
##  Tests if the language <L> is empty.
##  <L> must be in the category IsRatExpOnnLettersObj.
##
InstallGlobalFunction(IsEmptyLang, function(L)
    local aut;

    if IsRatExpOnnLettersObj(L) then
        aut := RatExpToAut(L);
    elif IsAutomaton(L) then
        aut := MinimalAutomaton(L);
    else
        Error("The argument to IsEmptyLang must be a rational expression or an automaton");
    fi;
    return(aut!.accepting = []);
end);

#############################################################################
#F  IsFullLang(<L>)
##
##  Tests if the language <L> is {alphabet}*.
##  <L> must be in the category IsRatExpOnnLettersObj.
##
InstallGlobalFunction(IsFullLang, function(L)
    local aut;

    if IsRatExpOnnLettersObj(L) then
        aut := RatExpToAut(L);
    elif IsAutomaton(L) then
        aut := MinimalAutomaton(L);
    else
        Error("The argument to IsEmptyLang must be a rational expression or an automaton");
    fi;
    return(aut!.states=1 and ForAll(aut!.transitions, i -> i = [1]));
end);

#############################################################################
# This is a common auxiliary function for IsContainedLang and AreDisjointLang.
BindGlobal("Automata_BONE_IsContainedLang", function(L1,L2)
    local   alph1,  alph2,  A1,  A2,  P;

    if not ((IsRationalExpression(L1) or IsAutomaton(L1)) and
            (IsRationalExpression(L2) or IsAutomaton(L2))) then
        Error("The arguments must be rational expressions or automata");
    fi;
    if IsAutomaton(L1) then
        alph1 := AlphabetOfAutomatonAsList(L1);
    else
        alph1 := AlphabetOfRatExpAsList(L1);
    fi;
    if IsAutomaton(L2) then
        alph2 := AlphabetOfAutomatonAsList(L2);
    else
        alph2 := AlphabetOfRatExpAsList(L2);
    fi;
    if alph1 <> alph2 then
        return(fail);
    fi;
    if IsAutomaton(L1) then
        A1 := MinimalAutomaton(L1);
    else
        A1 := RatExpToAut(L1);
    fi;
    if IsAutomaton(L2) then
        A2 := MinimalAutomaton(L2);
    else
        A2 := RatExpToAut(L2);
    fi;
    P := ProductAutomaton(A1,A2);
    return [P, AccessibleStates(P), A1, A2];
end);


#############################################################################
#F  IsContainedLang(<L1>,<L2>)
##
##  Tests if the language given through the rational expression or the
##  automaton <L1> is contained in the language given through the rational
## expression or the automaton <L2>.
##
## (For the correction of the algorithm, see the AMoRE manual, pg 124.)
##
InstallGlobalFunction(IsContainedLang, function(L1,L2)
    local   res,  P,  acc,  A1,  A2,  n1,  n2,  n,  s,  p,  q;

    res := Automata_BONE_IsContainedLang(L1, L2);
    if res = fail then
        Print("The given languages are not over the same alphabet","\n");
        return false;
    fi;
    P   := res[1];
    acc := res[2];
    A1  := res[3];
    A2  := res[4];
    n1 := A1!.states;
    n2 := A2!.states;
    n  := n1 * n2;
    for s in acc do
        if RemInt(s,n2) <> 0 then
            p := QuoInt(s,n2)+1;
            q := RemInt(s,n2);
        elif RemInt(s,n2) = 0 then
            p := QuoInt(s,n2);
            q := n2;
        fi;  ## s corresponds to (p,q) via a certain bijection (used in ProductAutomaton)
        if p in A1!.accepting and not q in A2!.accepting then
            return false;
        fi;
    od;
    return(true);
end);

############################################################################
#F  AreDisjointLang(<L1>,<L2>)
##
##  Tests if the languages given through the rational expression or the
##  automaton <L1> and the language given through the rational
## expression or the automaton <L2> are disjoint.
##
InstallGlobalFunction(AreDisjointLang, function(L1,L2)
    local   res,  P,  acc;

    res := Automata_BONE_IsContainedLang(L1, L2);
    if res = fail then
        Print("The given languages are not over the same alphabet","\n");
        return false;
    fi;
    P   := res[1];
    acc := res[2];
    if Intersection(acc,P!.accepting) = [] then
        return true;
    fi;
    return false;
end);

##########################################################################
##
#F  ProductRatExp(a,b)
##
##  Produces the product of two rational expressions over the same alphabet
##
InstallGlobalFunction(ProductRatExp,  function(a, b)
    local empty;
    if not (IsRatExpOnnLettersObj(a) and IsRatExpOnnLettersObj(b)) then
        Error("<a> and <b> must be rational expressions");
    elif not AlphabetOfRatExpAsList(a) = AlphabetOfRatExpAsList(b) then
        Error("<a> and <b> must be on the same alphabet");
    fi;
    empty := RatExpOnnLetters(AlphabetOfRatExpAsList(a), [], "empty_set");
    if a!.list_exp = "empty_set" or b!.list_exp = "empty_set" then
        return empty;
    fi;
    if a!.list_exp = [] then
        return b;
    elif b!.list_exp = [] then
        return a;
    fi;
    if a!.op = "product" and b!.op = "product" then
        return RatExpOnnLetters(AlphabetOfRatExpAsList(a),"product",
                       Concatenation(a!.list_exp, b!.list_exp ));
    elif a!.op = "product" then
        return RatExpOnnLetters(AlphabetOfRatExpAsList(a),"product",
                       Concatenation(a!.list_exp, [b] ));
    elif b!.op = "product" then
        return RatExpOnnLetters(AlphabetOfRatExpAsList(a),"product",
                       Concatenation( [a], b!.list_exp));
    else
        return RatExpOnnLetters(AlphabetOfRatExpAsList(a),"product", [a, b]);
    fi;
end);

#########################################################################
##
#F  UnionRatExp(a,b)
##
##  Produces the union of two rational expressions over the same alphabet
##
InstallGlobalFunction(UnionRatExp, function(a, b)
    if not (IsRatExpOnnLettersObj(a) and IsRatExpOnnLettersObj(b)) then
        Error("<a> and <b> must be rational expressions");
    elif not AlphabetOfRatExpAsList(a) = AlphabetOfRatExpAsList(b) then
        Error("<a> and <b> must be on the same alphabet");
    fi;
    if a!.list_exp = "empty_set" then
        return(b);
    elif b!.list_exp = "empty_set" then
        return(a);
    else
        return(RatExpOnnLetters(AlphabetOfRatExpAsList(a),"union",[a,b]));
    fi;
end);

#######################################################################
##
#F  StarRatExp(a)
##
##  Produces the star of a rational expression
##
InstallGlobalFunction(StarRatExp, function(a)
    if not IsRatExpOnnLettersObj(a) then
        Error("<a> must be rational expressions");
    fi;
    if a!.op = "star" then
        return a;
        else
        return RatExpOnnLetters(AlphabetOfRatExpAsList(a),"star", a);
    fi;
end);
#######################################################################

#E

Quelle rat-func.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.26 Sekunden (vorverarbeitet) ]