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