1############################################################################# 2## This program is free software: you can redistribute it and/or modify 3## it under the terms of the GNU General Public License as published by 4## the Free Software Foundation, either version 2 of the License, or 5## (at your option) any later version. 6## 7## This program is distributed in the hope that it will be useful, 8## but WITHOUT ANY WARRANTY; without even the implied warranty of 9## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10## GNU General Public License for more details. 11## 12#W automata.gi Ruth Hoffmann 13## 14## 15#Y Copyright (C) 2004-2015 School of Computer Science, 16#Y University of St. Andrews, North Haugh, 17#Y St. Andrews, Fife KY16 9SS, Scotland 18## 19 20################################################################################ 21## 22#F NDIntersectionAutomaton(aut1,aut2) 23## 24## A faster automata intersection algorithm, which does not turn the automata 25## deterministic. 26## 27InstallGlobalFunction(NDIntersectionAutomaton,function( a1, a2 ) 28 29local HashPair, ht, init, states, m, s1, s2, t1, t2, t, i, st, a, x, y, nst, he, finals, p, q, numofinitst,m1,m2; 30 31#These checks are from the original code 32if IsAutomaton( a1 ) then 33 ; 34elif IsRationalExpression( a1 ) then 35 a1 := RatExpToAut( a1 ); 36else 37 Error( "The first argument must be an automaton or a rational expression" ); 38fi; 39if IsAutomaton( a2 ) then 40 ; 41elif IsRationalExpression( a2 ) then 42 a2 := RatExpToAut( a2 ); 43else 44 Error( "The second argument must be an automaton or a rational expression" ); 45fi; 46 47if a1!.type = "epsilon" then 48 m1 := AlphabetOfAutomaton(a1)-1; 49else 50 m1 := AlphabetOfAutomaton(a1); 51fi; 52if a2!.type = "epsilon" then 53 m2 := AlphabetOfAutomaton(a2)-1; 54else 55 m2 := AlphabetOfAutomaton(a2); 56fi; 57if m1 <> m2 then 58 Error( "The arguments must be two automata over the same alphabet" ); 59fi; 60 61if a1!.type <> "epsilon" then 62 a1 := Automaton("epsilon", a1!.states, a1!.alphabet+1, Concatenation(a1!.transitions,[ListWithIdenticalEntries(a1!.states,[])]), a1!.initial, a1!.accepting); 63fi; 64if a2!.type <> "epsilon" then 65 a2 := Automaton("epsilon", a2!.states, a2!.alphabet+1, Concatenation(a2!.transitions,[ListWithIdenticalEntries(a2!.states,[])]), a2!.initial, a2!.accepting); 66fi; 67 68HashPair := function ( s ) 69 return HashKeyBag( s, 57, 0, 3*GAPInfo.BytesPerVariable ); 70end; 71ht := SparseHashTable( HashPair ); 72init := [ ]; 73for s1 in a1!.initial do 74 for s2 in a2!.initial do 75 Add(init, [ s1, s2 ]); 76 AddHashEntry( ht, [ s1, s2 ], Length( init ) ); 77 od; 78od; 79 80numofinitst:=Length(init); 81 82states := init; 83m := a1!.alphabet; 84i := 1; 85t1 := a1!.transitions; 86t2 := a2!.transitions; 87t := List( [ 1 .. m ], function ( x ) return [ ]; end ); 88 89while i <= Length( states ) do 90 st := states[i]; 91 for a in [ 1 .. m ] do 92 t[a][i] := [ ]; 93 if a = m then 94 for x in t1[a][st[1]] do 95 nst := [ x, st[2] ]; 96 MakeImmutable( nst ); 97 he := GetHashEntry( ht, nst ); 98 if he = fail then 99 Add( states, nst ); 100 he := Length( states ); 101 AddHashEntry( ht, nst, he ); 102 fi; 103 Add(t[a][i], he); 104 od; 105 for x in t2[a][st[2]] do 106 nst := [ st[1], x ]; 107 MakeImmutable( nst ); 108 he := GetHashEntry( ht, nst ); 109 if he = fail then 110 Add( states, nst ); 111 he := Length( states ); 112 AddHashEntry( ht, nst, he ); 113 fi; 114 Add(t[a][i], he); 115 od; 116 else 117 for x in t1[a][st[1]] do 118 for y in t2[a][st[2]] do 119 nst := [ x, y ]; 120 MakeImmutable( nst ); 121 he := GetHashEntry( ht, nst ); 122 if he = fail then 123 Add( states, nst ); 124 he := Length( states ); 125 AddHashEntry( ht, nst, he ); 126 fi; 127 Add(t[a][i], he); 128 od; 129 od; 130 fi; 131 od; 132 i := i + 1; 133od; 134finals := [ ]; 135for p in a1!.accepting do 136 for q in a2!.accepting do 137 he := GetHashEntry( ht, [ p, q ] ); 138 if he <> fail then 139 AddSet( finals, he ); 140 fi; 141 od; 142od; 143 144init := [ ]; 145for s1 in a1!.initial do 146 for s2 in a2!.initial do 147 he := GetHashEntry( ht, [ s1, s2 ] ); 148 if he <> fail then 149 Add( init, he ); 150 fi; 151 od; 152od; 153 154return Automaton( "epsilon", Length( states ), AlphabetOfAutomatonAsList( a1 ), t, [ 1 .. numofinitst ], finals ); 155 156end ); 157 158################################################################################ 159## 160#F NDUnionAutomata(aut1,aut2) 161## 162## A faster automata union algorithm, which does not turn the automata 163## deterministic. 164## 165InstallGlobalFunction(NDUnionAutomata,function( A, B ) 166local QA, T, a, i, I, F, mA,mB; 167 168if not (IsAutomatonObj( A ) and IsAutomatonObj( B )) then 169 Error( "The arguments must be two automata" ); 170fi; 171 172if A!.type = "epsilon" then 173 mA := AlphabetOfAutomaton(A)-1; 174else 175 mA := AlphabetOfAutomaton(A); 176fi; 177if B!.type = "epsilon" then 178 mB := AlphabetOfAutomaton(B)-1; 179else 180 mB := AlphabetOfAutomaton(B); 181fi; 182if mA <> mB then 183 Error( "The arguments must be two automata over the same alphabet" ); 184fi; 185 186QA := A!.states; 187T := List( A!.transitions, ShallowCopy ); 188if A!.type <> "epsilon" and B!.type = "epsilon" then 189 Add(T,[]); 190fi; 191 192for a in [ 1 .. B!.alphabet ] do 193 for i in [ 1 .. B!.states ] do 194 if B!.transitions[a][i] = 0 then 195 T[a][QA + i] := 0; 196 else 197 T[a][QA + i] := QA + B!.transitions[a][i]; 198 fi; 199 od; 200od; 201if A!.type = "epsilon" and B!.type <> "epsilon" then 202 for i in [1..B!.states] do 203 Add(T[mA+1],0); 204 od; 205fi; 206I := ShallowCopy( A!.initial ); 207Append( I, QA + B!.initial ); 208 209F := ShallowCopy( A!.accepting ); 210Append( F, QA + B!.accepting ); 211 212if A!.type = "epsilon" or B!.type = "epsilon" then 213 return Automaton( "epsilon", QA + B!.states, mA+1, T, I, F ); 214else 215 return Automaton( "nondet", QA + B!.states, AlphabetOfAutomatonAsList( A ), T, I, F ); 216fi; 217end ); 218 219################################################################################ 220## 221#F NDProductOfLanguages(aut1,aut2) 222## 223## A faster automata concatenation algorithm, which does not turn the automata 224## deterministic. 225## 226InstallGlobalFunction(NDProductOfLanguages, function ( a1, a2 ) 227local T, a, q, s, A,x,m,m1,m2; 228 229if a1!.type = "epsilon" then 230 m1 := AlphabetOfAutomaton(a1)-1; 231else 232 m1 := AlphabetOfAutomaton(a1); 233fi; 234if a2!.type = "epsilon" then 235 m2 := AlphabetOfAutomaton(a2)-1; 236else 237 m2 := AlphabetOfAutomaton(a2); 238fi; 239if m1 <> m2 then 240 Error( "The arguments must be two automata over the same alphabet" ); 241fi; 242 243if a1!.type = "det" then 244 T := List( a1!.transitions, function ( l ) return List( l, function ( q ) return [ q ]; end ); end ); 245else 246 T := List( a1!.transitions, ShallowCopy ); 247fi; 248 249if a1!.type <> "epsilon" then 250 Add( T, List( [ 1 .. a1!.states], function ( i ) return [ ]; end ) ); 251fi; 252for a in [ 1 .. a2!.alphabet ] do 253 for q in [ 1 .. a2!.states ] do 254 if a2!.transitions[a][q] = 0 then 255 Add( T[a], [ ] ); 256 else 257 x := a2!.transitions[a][q] + a1!.states; 258 if IsList(x) then 259 Add(T[a],x); 260 else 261 Add(T[a],[x]); 262 fi; 263 fi; 264 od; 265od; 266m := Length(T); 267 268if a2!.type <> "epsilon" then 269 for q in [1 .. a2!.states] do 270 Add(T[m],[]); 271 od; 272fi; 273 274for q in a1!.accepting do 275 for s in a2!.initial do 276 Add( T[m][q], a1!.states + s ); 277 od; 278od; 279A := Automaton( "epsilon", a1!.states + a2!.states, m, T, ShallowCopy( a1!.initial ), List( a2!.accepting, function ( q ) return q + a1!.states; end ) ); 280 281return A; 282 283end ); 284