Repository navigation
Expand file tree
/
Copy pathSymmDiff.java
More file actions
74 lines (52 loc) · 1.96 KB
/
Copy pathSymmDiff.java
File metadata and controls
74 lines (52 loc) · 1.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.*;
public class SymmDiff {
public static boolean print = true;
public static DFA calcDiff(DFA d1, DFA d2) {
//(Comp(D1) n D2) u (D2 n Comp(D1))
//Create copy of original DFAs as they get changed when calculating complement
//initD1 = initial dfa, not to be confused with IntD1 which is the result of the intersection
DFA initD1 = new DFA(d1);
DFA initD2 = new DFA(d2);
//First part of result
//let a = (Complement(S) n T)
DFA comp = Complement.calcComplementNoPrint(d1);
DFA IntD1 = Intersection.calcIntersectionNoPrint(comp, initD2);
//Second part of result
//let b = (S n Complement(T))
DFA comp2 = Complement.calcComplementNoPrint(d2);
DFA IntD2 = Intersection.calcIntersectionNoPrint(initD1, comp2);
//Final part of result
//a u b
//Calculated by taking intersection and then modifying the final states
//Such that the set of all final states F* = set of all states (r,s)
//such that r is a final state of IntD1 OR s is a final state of IntD2
DFA union = Intersection.calcIntersection(IntD1, IntD2);
ArrayList<String> newFStates = new ArrayList<String>();
//Get accept states of both intersections
//Final states are pairs (s,j) where s is a final state in DFA 1 or of DFA 2
for(String d1Accept : IntD1.getFinalStates()) {
for(String d2States : IntD2.getStates()) {
newFStates.add(d1Accept + d2States);
}
}
for(String d1States : IntD1.getStates()) {
for(String d2Accept : IntD2.getFinalStates()) {
newFStates.add(d1States + d2Accept);
}
}
//Convert to set to get rid of unwanted values
Set<String> setFinalStates = new HashSet<String>();
for(String s : newFStates) {
setFinalStates.add(s);
}
newFStates.clear();
newFStates.addAll(setFinalStates);
union.setFinalStates(newFStates);
if(print)union.printAll();
return union;
}
public static DFA calcDiffNoPrint(DFA d1, DFA d2) {
print = false;
return calcDiff(d1,d2);
}
}