Spracherkennung für: .gi vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]
#############################################################################
##
#W ExtAutom.gi FGA package Christian Sievers
##
## Methods to create and compute with extended inverse automata
##
#Y 2003 - 2016
##
BindGlobal( "FGA_FreeGroupForGenerators", FreeGroup(infinity) );
BindGlobal( "FGA_One", One(FGA_FreeGroupForGenerators) );
InstallGlobalFunction( FGA_newstateX,
function()
return (rec (delta:=[], deltainv:=[], sndsig:=[], sndsiginv:=[]));
end );
InstallGlobalFunction( FGA_connectposX,
function(s1, s2, g, sndsig, sndsiginv)
s1.delta[g] := s2;
s2.deltainv[g] := s1;
s1.sndsig[g] := sndsig;
s2.sndsiginv[g] := sndsiginv;
end );
InstallGlobalFunction( FGA_connectX,
function(s1, s2, g, sndsig)
if g>0 then
FGA_connectposX(s1, s2, g, sndsig, sndsig^-1);
else
FGA_connectposX(s2, s1, -g, sndsig^-1, sndsig);
fi;
end );
InstallGlobalFunction( FGA_defineX,
function(state, gen)
local nstate;
nstate := FGA_newstateX();
FGA_connectX(state, nstate, gen, FGA_One);
# nstate.W := state.W * gen
return nstate;
end );
# active
InstallGlobalFunction( FGA_findX,
function(s)
local sndsig;
sndsig := FGA_One;
while IsBound(s.isnow) do
sndsig := sndsig * s.sndcoinc;
s := s.isnow;
od;
return rec(state:=s, sndcoinc:=sndsig);
# todo: path compression
end );
InstallGlobalFunction( FGA_mergeX,
function(s1, A, s2, B, Q)
local s, C;
s1 := FGA_findX(s1);
s2 := FGA_findX(s2);
if IsNotIdenticalObj(s1.state,s2.state) then
if IsBound(s2.state.isinitial) then
# don't mess with the initial state
s := s1; s1 := s2; s2 := s;
C := A; A := B; B := C;
fi;
s2.state.isnow := s1.state;
s2.state.sndcoinc := (B*s2.sndcoinc)^-1*A*s1.sndcoinc;
Add(Q,s2.state);
fi;
end );
InstallGlobalFunction( FGA_coincidenceX,
function(s1, A, s2, B)
local Q, s, g, s0, s01, delta, deltainv;
Q := [];
FGA_mergeX(s1, A, s2, B, Q);
for s in Q do
delta := ShallowCopy(s.delta);
for g in BoundPositions(delta) do
Unbind(delta[g].deltainv[g]);
od;
deltainv := ShallowCopy(s.deltainv);
for g in BoundPositions(deltainv) do
Unbind(deltainv[g].delta[g]);
od;
for g in BoundPositions(delta) do
s0 := FGA_findX(s);
s01 := FGA_findX(delta[g]);
if IsBound(s0.state.delta[g]) then
FGA_mergeX(s01.state, s.sndsig[g]*s01.sndcoinc,
s0.state.delta[g], s0.sndcoinc*s0.state.sndsig[g], Q);
elif IsBound(s01.state.deltainv[g]) then
FGA_mergeX(s0.state, s.sndsig[g]^-1*s0.sndcoinc,
s01.state.deltainv[g],
s01.sndcoinc*s01.state.sndsiginv[g], Q);
else
FGA_connectX(s0.state, s01.state, g,
s0.sndcoinc^-1*s.sndsig[g]*s01.sndcoinc);
fi;
od;
for g in BoundPositions(deltainv) do
s0 := FGA_findX(s);
s01 := FGA_findX(deltainv[g]);
if IsBound(s0.state.deltainv[g]) then
FGA_mergeX(s01.state, s.sndsiginv[g]*s01.sndcoinc,
s0.state.deltainv[g], s0.sndcoinc*s0.state.sndsiginv[g], Q);
elif IsBound(s01.state.delta[g]) then
FGA_mergeX(s0.state, s.sndsiginv[g]^-1*s0.sndcoinc,
s01.state.delta[g], s01.sndcoinc*s01.state.sndsig[g], Q);
else
FGA_connectX(s01.state, s0.state, g,
s01.sndcoinc^-1*s.sndsiginv[g]^-1*s0.sndcoinc);
fi;
od;
od;
end );
InstallGlobalFunction( FGA_atfX,
function(l, lx, p)
if IsBound(l[p]) then
return rec(state:=l[p], sndsig:=lx[p]);
else
return fail;
fi;
end );
InstallGlobalFunction( FGA_deltaX,
function(state, gen)
if gen>0 then
return FGA_atfX(state.delta, state.sndsig, gen);
else
return FGA_atfX(state.deltainv, state.sndsiginv, -gen);
fi;
end );
InstallGlobalFunction( FGA_stepX,
function(r, gen)
local res;
res := FGA_deltaX(r.state, gen);
if res <> fail then
res.sndsig := r.sndsig * res.sndsig;
fi;
return res;
end );
InstallGlobalFunction( FGA_deltasX,
function(state, genlist)
return IteratedF(genlist, FGA_stepX, rec(state:=state, sndsig:=FGA_One));
end );
InstallGlobalFunction( FGA_traceX,
function(s,w)
local i, s1;
s := rec(state := s, sndsig := FGA_One);
s1 := s;
i := 1;
while i <= Length(w) and s1 <> fail do
s := s1;
s1 := FGA_stepX(s, w[i]);
i := i+1;
od;
if s1 = fail then
return rec(state:=s.state, index:=i-1, sndsig:=s.sndsig);
else
return rec(state:=s1.state, index:=i, sndsig:=s1.sndsig);
fi;
end );
InstallGlobalFunction( FGA_backtraceX,
function(s,w,j)
local i, s1;
s := rec(state:=s, sndsig := FGA_One);
s1 := s;
i := Length(w);
while i >= j and s1 <> fail do
s := s1;
s1 := FGA_stepX(s, -w[i]);
i := i-1;
od;
if s1 = fail then
return rec(state:=s.state, index:=i+1, sndsig:=s.sndsig );
else
return rec(state:=s1.state, index:=i, sndsig:=s1.sndsig);
fi;
end );
InstallGlobalFunction( FGA_insertgeneratorX,
function(s, g, sndgen)
local i, t, bt, s1, s2;
t := FGA_traceX(s, g);
bt := FGA_backtraceX(s, g, t.index);
s1 := t.state;
s2 := bt.state;
if t.index > bt.index then # trace complete
FGA_coincidenceX(s1, sndgen^-1*t.sndsig, s2, bt.sndsig);
else
if IsIdenticalObj(s1, s2) then
while g[t.index] = -g[bt.index] do
s1 := FGA_defineX(s1, g[t.index]);
t.index := t.index+1;
bt.index := bt.index - 1;
od;
s2 := s1;
fi;
for i in [t.index .. bt.index-1] do
s1 := FGA_defineX(s1, g[i]);
od;
FGA_connectX(s1, s2, g[bt.index], t.sndsig^-1*sndgen*bt.sndsig);
fi;
return FGA_find(s);
end );
InstallGlobalFunction( FGA_fromgeneratorsX,
function(gens)
local gen, i, autom;
i := 1;
autom := FGA_newstateX();
autom.isinitial := true;
for gen in gens do
autom := FGA_insertgeneratorX(autom, gen,
FGA_FreeGroupForGenerators.(i) );
i := i+1;
od;
return autom;
end );
InstallGlobalFunction( FGA_FromGroupWithGeneratorsX,
function( G )
return FGA_fromgeneratorsX( List ( GeneratorsOfGroup ( G ),
LetterRepAssocWord ));
end );
InstallGlobalFunction( FGA_AsWordLetterRepInGenerators,
function( w, A)
local res;
res := FGA_deltasX( A, w );
if res = fail or IsNotIdenticalObj( res.state, A ) then
return fail;
else
return LetterRepAssocWord( res.sndsig );
fi;
end );
#############################################################################
##
#E
