Commits

Fernando G N Rocha committed a2a0e5c

to_minimum implemented, polish needed, tests missing

Comments (0)

Files changed (1)

                     raise TypeError, 'Not an DFA'
 
 
+    def to_minimum(self):
+        '''Minimize the DFA to it's minimum, classic algorithm'''
+        not_marked = []
+        results = {}
+        states = self.states[:]
         
+        # populate not_final
+        not_final = self.states[:]
+        for state in self.final_states:
+            not_final.remove(state)
+
+
+        # Add auxliar state if DFA is not complete
+        for inner in self.delta.values():
+            if len(inner) < 2:
+                states.append('ex')
+                not_final.append('ex')
+                break
+
+        # Populate not_marked
+        for state in states[:]:
+            states.remove(state)
+            for _state in states:
+                not_marked.append(set([state,_state]))
+
+        # Remove marked from not_marked 
+        for state in not_final:
+            for _state in self.final_states:
+                not_marked.remove(set([state,_state]))
+
+
+        def res_states(duple):
+            '''Recieve a pair of states, check result against each symbol'''
+            import pdb
+            res_list = []
+            for symbol in self.alphabet:
+                res = ()
+                for state in duple:
+                    # Check each state of duple 
+                    if state != 'ex' and self.delta[state].get(symbol):
+                        res += (self.delta[state][symbol][:].pop(),)
+                    else:
+                        res += ('ex',)
+                #if duple == set(['e2','e4']):
+                #    pdb.set_trace()
+                if len(set(res)) == 2 and set(res) not in not_marked:
+                    # Se res estiver marcado
+                    not_marked.remove(duple)
+                    # Check if duple is result of before check, if so remove
+                    if tuple(duple) in results:
+                        for pair in results[tuple(duple)]:
+                            try:
+                                not_marked.remove(set(pair))
+                            except:
+                                # Pair already removed
+                                pass
+                    return 
+                #if len(res) > 1: #TODO: remove redundancy
+                res_list.append(res)
+            return res_list
+       
+
+        # Check for all not_marked
+        for t in not_marked[:]:
+            res = res_states(t)
+            if res:
+                for i in res:
+                    #Add to results
+                    if results.get(i):
+                        results[i].append(tuple(t))
+                    else:
+                        results[i] = [tuple(t)]
+
+
+        # Construct new DFA if DFA is not minimum
+        if not not_marked:
+            print ('DFA is the minimum DFA')
+            return self
+
+        # Check if a state is equivalent to other, if so, remove it's equivalent
+        delta = {}
+        states = self.states[:]
+        eq_table = []
+
+
+        def eq_states(state):
+            '''Usefull when there is 3 or more eq states'''
+            for i in range(len(not_marked)):
+                if state in not_marked[i]:
+                    not_marked[i].remove(state)
+                    eq_state = not_marked[i].pop()
+
+                    states.remove(eq_state)
+                    del(not_marked[i])
+
+                    return [eq_state] + eq_states(eq_state)
+            return []
+
+        for state in states:
+            eq_table += [tuple([state] + eq_states(state))]
+
+        eq_dict = {}
+        for i in range(len(eq_table)):
+            eq_dict[eq_table[i]] = 'f'+ str(i)
+            for state in eq_table[i]:
+                eq_dict[(state,)] = 'f' + str(i) 
+
+
+        # Populate delta
+        for i in range(len(eq_table)):
+            delta['f' + str(i)] = {}
+            
+        def union(states, symbol):
+            res_states = set()
+            for state in states:
+                _state = self.delta[state].get(symbol)
+                if _state:
+                    res_states.add(_state[:].pop())
+            return eq_dict[tuple(res_states)]
+           
+
+        # Construct delta
+        for i in range(len(eq_table)):
+            for symbol in self.alphabet:
+                delta['f' + str(i)][symbol] = [union(eq_table[i], symbol)]
+
+        # Set final states
+        final = set()
+        for states in eq_dict:
+            for state in states:
+                if state in self.final_states:
+                    final.add(eq_dict[states])
+        final = list(final) 
+
+
+        return DFA(self.alphabet, final, delta)
+
+
+
         
+
+
+delta1 = {'e0': {'0': ['e1']}, 
+                          'e1': {'1': ['e2']},
+                          'e2': {'0': ['e1'], '1': ['e3']},
+                          'e3': {'0': ['e4']},
+                          'e4': {'0': ['e5'], '1': ['e6']},
+                          'e5': {'0': ['e5']},
+                          'e6': {'0': ['e7']},
+                          'e7': {'1': ['e4']}}
+A1 = DFA(['0','1'], ['e2', 'e3', 'e4', 'e5', 'e6'] , delta1)
+print (A1.to_minimum())
+print 
+print '###########################################'
+print
+delta = {'e0': {'0':['e1'], '1':['e2']},
+         'e1': {'0':['e1'], '1':['e2']},
+         'e2': {'0':['e3'], '1':['e2']},
+         'e3': {'0':['e3'], '1':['e2']}}
+A = DFA(['0','1'], ['e2', 'e3'] , delta)
+print A.to_minimum()