|
#############################################################################
## This program is free software: you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation, either version 2 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
## GNU General Public License for more details.
##
#W automata.gi Ruth Hoffmann
##
##
#Y Copyright (C) 2004-2015 School of Computer Science,
#Y University of St. Andrews, North Haugh,
#Y St. Andrews, Fife KY16 9SS, Scotland
##
################################################################################
##
#F NDIntersectionAutomaton(aut1,aut2)
##
## A faster automata intersection algorithm, which does not turn the automata
## deterministic.
##
InstallGlobalFunction(NDIntersectionAutomaton,function( a1, a2 )
local HashPair, ht, init, states, m, s1, s2, t1, t2, t, i, st, a, x, y, nst, he, finals, p, q, numofinitst,m1,m2;
#These checks are from the original code
if IsAutomaton( a1 ) then
;
elif IsRationalExpression( a1 ) then
a1 := RatExpToAut( a1 );
else
Error( "The first argument must be an automaton or a rational expression" );
fi;
if IsAutomaton( a2 ) then
;
elif IsRationalExpression( a2 ) then
a2 := RatExpToAut( a2 );
else
Error( "The second argument must be an automaton or a rational expression" );
fi;
if a1!.type = "epsilon" then
m1 := AlphabetOfAutomaton(a1)-1;
else
m1 := AlphabetOfAutomaton(a1);
fi;
if a2!.type = "epsilon" then
m2 := AlphabetOfAutomaton(a2)-1;
else
m2 := AlphabetOfAutomaton(a2);
fi;
if m1 <> m2 then
Error( "The arguments must be two automata over the same alphabet" );
fi;
if a1!.type <> "epsilon" then
a1 := Automaton("epsilon", a1!.states, a1!.alphabet+1, Concatenation(a1!.transitions,[ListWithIdenticalEntries(a1!.states,[])]), a1!.initial, a1!.accepting);
fi;
if a2!.type <> "epsilon" then
a2 := Automaton("epsilon", a2!.states, a2!.alphabet+1, Concatenation(a2!.transitions,[ListWithIdenticalEntries(a2!.states,[])]), a2!.initial, a2!.accepting);
fi;
HashPair := function ( s )
return HashKeyBag( s, 57, 0, 3*GAPInfo.BytesPerVariable );
end;
ht := SparseHashTable( HashPair );
init := [ ];
for s1 in a1!.initial do
for s2 in a2!.initial do
Add(init, [ s1, s2 ]);
AddHashEntry( ht, [ s1, s2 ], Length( init ) );
od;
od;
numofinitst:=Length(init);
states := init;
m := a1!.alphabet;
i := 1;
t1 := a1!.transitions;
t2 := a2!.transitions;
t := List( [ 1 .. m ], function ( x ) return [ ]; end );
while i <= Length( states ) do
st := states[i];
for a in [ 1 .. m ] do
t[a][i] := [ ];
if a = m then
for x in t1[a][st[1]] do
nst := [ x, st[2] ];
MakeImmutable( nst );
he := GetHashEntry( ht, nst );
if he = fail then
Add( states, nst );
he := Length( states );
AddHashEntry( ht, nst, he );
fi;
Add(t[a][i], he);
od;
for x in t2[a][st[2]] do
nst := [ st[1], x ];
MakeImmutable( nst );
he := GetHashEntry( ht, nst );
if he = fail then
Add( states, nst );
he := Length( states );
AddHashEntry( ht, nst, he );
fi;
Add(t[a][i], he);
od;
else
for x in t1[a][st[1]] do
for y in t2[a][st[2]] do
nst := [ x, y ];
MakeImmutable( nst );
he := GetHashEntry( ht, nst );
if he = fail then
Add( states, nst );
he := Length( states );
AddHashEntry( ht, nst, he );
fi;
Add(t[a][i], he);
od;
od;
fi;
od;
i := i + 1;
od;
finals := [ ];
for p in a1!.accepting do
for q in a2!.accepting do
he := GetHashEntry( ht, [ p, q ] );
if he <> fail then
AddSet( finals, he );
fi;
od;
od;
init := [ ];
for s1 in a1!.initial do
for s2 in a2!.initial do
he := GetHashEntry( ht, [ s1, s2 ] );
if he <> fail then
Add( init, he );
fi;
od;
od;
return Automaton( "epsilon", Length( states ), AlphabetOfAutomatonAsList( a1 ), t, [ 1 .. numofinitst ], finals );
end );
################################################################################
##
#F NDUnionAutomata(aut1,aut2)
##
## A faster automata union algorithm, which does not turn the automata
## deterministic.
##
InstallGlobalFunction(NDUnionAutomata,function( A, B )
local QA, T, a, i, I, F, mA,mB;
if not (IsAutomatonObj( A ) and IsAutomatonObj( B )) then
Error( "The arguments must be two automata" );
fi;
if A!.type = "epsilon" then
mA := AlphabetOfAutomaton(A)-1;
else
mA := AlphabetOfAutomaton(A);
fi;
if B!.type = "epsilon" then
mB := AlphabetOfAutomaton(B)-1;
else
mB := AlphabetOfAutomaton(B);
fi;
if mA <> mB then
Error( "The arguments must be two automata over the same alphabet" );
fi;
QA := A!.states;
T := List( A!.transitions, ShallowCopy );
if A!.type <> "epsilon" and B!.type = "epsilon" then
Add(T,[]);
fi;
for a in [ 1 .. B!.alphabet ] do
for i in [ 1 .. B!.states ] do
if B!.transitions[a][i] = 0 then
T[a][QA + i] := 0;
else
T[a][QA + i] := QA + B!.transitions[a][i];
fi;
od;
od;
if A!.type = "epsilon" and B!.type <> "epsilon" then
for i in [1..B!.states] do
Add(T[mA+1],0);
od;
fi;
I := ShallowCopy( A!.initial );
Append( I, QA + B!.initial );
F := ShallowCopy( A!.accepting );
Append( F, QA + B!.accepting );
if A!.type = "epsilon" or B!.type = "epsilon" then
return Automaton( "epsilon", QA + B!.states, mA+1, T, I, F );
else
return Automaton( "nondet", QA + B!.states, AlphabetOfAutomatonAsList( A ), T, I, F );
fi;
end );
################################################################################
##
#F NDProductOfLanguages(aut1,aut2)
##
## A faster automata concatenation algorithm, which does not turn the automata
## deterministic.
##
InstallGlobalFunction(NDProductOfLanguages, function ( a1, a2 )
local T, a, q, s, A,x,m,m1,m2;
if a1!.type = "epsilon" then
m1 := AlphabetOfAutomaton(a1)-1;
else
m1 := AlphabetOfAutomaton(a1);
fi;
if a2!.type = "epsilon" then
m2 := AlphabetOfAutomaton(a2)-1;
else
m2 := AlphabetOfAutomaton(a2);
fi;
if m1 <> m2 then
Error( "The arguments must be two automata over the same alphabet" );
fi;
if a1!.type = "det" then
T := List( a1!.transitions, function ( l ) return List( l, function ( q ) return [ q ]; end ); end );
else
T := List( a1!.transitions, ShallowCopy );
fi;
if a1!.type <> "epsilon" then
Add( T, List( [ 1 .. a1!.states], function ( i ) return [ ]; end ) );
fi;
for a in [ 1 .. a2!.alphabet ] do
for q in [ 1 .. a2!.states ] do
if a2!.transitions[a][q] = 0 then
Add( T[a], [ ] );
else
x := a2!.transitions[a][q] + a1!.states;
if IsList(x) then
Add(T[a],x);
else
Add(T[a],[x]);
fi;
fi;
od;
od;
m := Length(T);
if a2!.type <> "epsilon" then
for q in [1 .. a2!.states] do
Add(T[m],[]);
od;
fi;
for q in a1!.accepting do
for s in a2!.initial do
Add( T[m][q], a1!.states + s );
od;
od;
A := Automaton( "epsilon", a1!.states + a2!.states, m, T, ShallowCopy( a1!.initial ), List( a2!.accepting, function ( q ) return q + a1!.states; end ) );
return A;
end );
[ Dauer der Verarbeitung: 0.27 Sekunden
(vorverarbeitet)
]
|
