1    import java.util.*; 
2    import java.util.Map.Entry; 
3     
4    /** 
5     * Created by IntelliJ IDEA. 
6     * Code By: Bo Li, libo@libo.me 
7     * Date: 2009-12-10 
8     * Time: 15:27:37 
9     * CBIT, Roskilde University 
10    */ 
11   public class NFA { 
12       private int iState; 
13       private int aState; 
14       Map<Integer, ArrayList<transition>> trans; 
15    
16       public NFA(int iState, int aState) { 
17           this.iState = iState; 
18           this.aState = aState; 
19           trans = new HashMap<Integer, ArrayList<transition>>(); 
20           trans.put(iState, new ArrayList<transition>()); 
21       } 
22    
23       public void AddTransitions(int s1, int s2, String lab) { 
24           ArrayList<transition> transitions = new ArrayList<transition>(); 
25           if (trans.containsKey(s1)) 
26               trans.get(s1).add(new transition(s1, s2, lab)); 
27           else { 
28               transitions = new ArrayList<transition>(); 
29               trans.put(s1, transitions); 
30           } 
31           transitions.add(new transition(s1, s2, lab)); 
32       } 
33    
34       public int Start() { 
35           return iState; 
36       } 
37    
38       public int Exit() { 
39           return aState; 
40       } 
41    
42       public String toString() { 
43           return "NFA start->" + iState + "  trans-> " + trans + " exit->" + aState; 
44       } 
45    
46       public static class stateName { 
47           public static int nextState = 0; 
48    
49           public int next() { 
50               return nextState++; 
51           } 
52       } 
53    
54       public static Set<Integer> GetLambdaClosure(Set<Integer> S, Map<Integer, ArrayList<transition>> trans) { 
55           Queue<Integer> worklist = new LinkedList<Integer>(); 
56           worklist.addAll(S); 
57           Set<Integer> LamClosure = new HashSet<Integer>(); 
58           LamClosure.addAll(S); 
59           while (!worklist.isEmpty()) { 
60               int s = worklist.poll(); 
61               if (trans.containsKey(s)) { 
62                   for (transition t : trans.get(s)) { 
63                       if (t.lab == "lambda" && !LamClosure.contains(t.nextState)) { 
64                           LamClosure.add(t.nextState); 
65                           worklist.offer(t.nextState); 
66                       } 
67                   } 
68               } 
69           } 
70           return LamClosure; 
71    
72       } 
73    
74       public static Set<Integer> GetLambdaClosure(int i, Map<Integer, ArrayList<transition>> trans) { 
75           Set<Integer> j = new HashSet<Integer>(); 
76           j.add(i); 
77           Set<Integer> LambdaClosure = GetLambdaClosure(j, trans); 
78           return LambdaClosure; 
79       } 
80    
81       public static Map<Set<Integer>, Integer> newState(Set<Set<Integer>> states) { 
82           Map<Set<Integer>, Integer> nState = new HashMap<Set<Integer>, Integer>(); 
83           int i = 0; 
84           for (Set<Integer> s : states) { 
85               nState.put(s, i); 
86               i++; 
87           } 
88           return nState; 
89       } 
90    
91       public static Map<Integer, Map<String, Integer>> getTrans(Map<Set<Integer>, Integer> newStates, Map<Set<Integer>, Map<String, Set<Integer>>> trs) { 
92           Map<Integer, Map<String, Integer>> newTrans = new HashMap<Integer, Map<String, Integer>>(); 
93           for (Entry<Set<Integer>, Map<String, Set<Integer>>> entry : trs.entrySet()) { 
94               Set<Integer> i = entry.getKey(); 
95               Map<String, Integer> tempTrans = new HashMap<String, Integer>(); 
96               for (String a : entry.getValue().keySet()) { 
97                   tempTrans.put(a, newStates.get(entry.getValue().get(a))); 
98               } 
99               newTrans.put(newStates.get(i), tempTrans); 
100          } 
101   
102          return newTrans; 
103      } 
104   
105      public static Map<Set<Integer>, Map<String, Set<Integer>>> NfaToDfaTrans(int start, Map<Integer, ArrayList<transition>> trans) { 
106          Map<Set<Integer>, Map<String, Set<Integer>>> DfaTrans = new HashMap<Set<Integer>, Map<String, Set<Integer>>>(); 
107   
108          Set<Integer> Start = GetLambdaClosure(start, trans); 
109          Queue<Set<Integer>> TempRunLoopUse = new LinkedList<Set<Integer>>(); 
110          TempRunLoopUse.offer(Start); 
111          while (!TempRunLoopUse.isEmpty()) { 
112              Set<Integer> S = TempRunLoopUse.poll(); 
113              if (!DfaTrans.containsKey(S)) { 
114                  Map<String, Set<Integer>> newTrans = new HashMap<String, Set<Integer>>(); 
115                  for (int s : S) 
116                      if (trans.containsKey(s)) { 
117                          for (transition t : trans.get(s)) { 
118                              if (t.lab != "lambda") { 
119                                  Set<Integer> nextStates; 
120                                  if (newTrans.containsKey(t.lab)) 
121                                      nextStates = newTrans.get(t.lab); 
122                                  else { 
123                                      nextStates = new HashSet<Integer>(); 
124                                      newTrans.put(t.lab, nextStates); 
125                                  } 
126                                  nextStates.add(t.nextState); 
127                              } 
128                          } 
129                      } 
130   
131                  Map<String, Set<Integer>> newTransClosed = new HashMap<String, Set<Integer>>(); 
132                  for (Entry<String, Set<Integer>> entry : newTrans.entrySet()) { 
133                      Set<Integer> close = GetLambdaClosure(entry.getValue(), trans); 
134                      newTransClosed.put(entry.getKey(), close); 
135                      TempRunLoopUse.offer(close); 
136                  } 
137                  DfaTrans.put(S, newTransClosed); 
138              } 
139          } 
140          return DfaTrans; 
141      } 
142   
143      public static Set<Integer> GetAcceptStates(Set<Set<Integer>> states, 
144                                                 Map<Set<Integer>, Integer> nState, int exit) { 
145   
146          Set<Integer> iAcStates = new HashSet<Integer>(); 
147          for (Set<Integer> s : states) { 
148              if (s.contains(exit)) 
149                  iAcStates.add(nState.get(s)); 
150          } 
151          return iAcStates; 
152      } 
153   
154      public DFA NfaToDfa() { 
155          Map<Set<Integer>, Map<String, Set<Integer>>> NToDTrans = NfaToDfaTrans(iState, trans); 
156          System.out.println("NFA to DFA transitions->" + NToDTrans); 
157   
158          Set<Integer> NToDStart = GetLambdaClosure(iState, trans); 
159          System.out.println("NFA to DFA new start states->" + NToDStart); 
160   
161          Map<Set<Integer>, Integer> NState = newState(NToDTrans.keySet()); 
162          System.out.println("new name of states collection->" + NState); 
163   
164          Map<Integer, Map<String, Integer>> NToDNState = getTrans(NState, NToDTrans); 
165          System.out.println("NFA to DFA new states->" + NToDNState); 
166   
167          int NToDnStart = NState.get(NToDStart); 
168          System.out.println("NFA to DFA start state->" + NToDnStart); 
169   
170          Set<Integer> NToDSAState = GetAcceptStates(NToDTrans.keySet(), NState, aState); 
171          System.out.println("NFA to DFA new accept state->" + NToDSAState); 
172          return new DFA(NToDnStart, NToDSAState, NToDNState); 
173      } 
174  } 
175   
176