Commits

Fernando G N Rocha committed b4ac3a6

Implemented to_DFA, tests missing

  • Participants
  • Parent commits c002602

Comments (0)

Files changed (3)

+#!/usr/bin/python
+'''
+Automata Simplification
+
+Author: Fernando Rocha
+E-mail: fernandogrd@yahoo.com.br
+'''
+
+from automaton import Automaton
+
+class DFA(Automaton):
+    '''Represent an non-deterministic finite automaton'''
+
+    def __init__ (self, alphabet, final_states, delta):
+        Automaton.__init__(self, alphabet, final_states, delta)
+
+        # Verifies if it is an DFA
+        if 'E' in alphabet:
+            raise TypeError, 'Not an DFA'
+        for state in delta:
+            for symbol in delta[state]:
+                if len(delta[state][symbol]) > 1:
+                    raise TypeError, 'Not an DFA'
+
+
+        
+        
                 if states:
                     res +=  [_state for _state in states if _state not in res]
             return tuple(res)
-        
+
+        def final_states(h_delta):
+            final = []
+            for state in h_delta:
+                for states in h_delta[state].values():
+                    for _state in states:
+                        if state not in final and _state in self.final_states:
+                            final += [state]
+            return final
+
         aux_to_DFA([self.initial])
         new_delta = {}
         for key, value in delta.items():
             new_delta[ref_table[key]] = value
+        final = final_states(new_delta)
         for state in new_delta:
             for symbol, value in new_delta[state].items():
-                new_delta[state][symbol] = ref_table[value]
+                new_delta[state][symbol] = [ref_table[value]] #change to tuple?
 
-        return new_delta
-        # return DFA(self.alphabet, TODO:final_states, new_delta)
+        return DFA(self.alphabet, final, new_delta)
 
-        #return  res_state([self.states[0]],self.alphabet[0])
-
-Q0 = {'0': ['q1','q2']}
-Q1 = {'1': ['q1','q2','q3']}
-Q2 = {'1': ['q1','q2','q3']}
-Q3 = {}
-delta = {'q0':Q0, 'q1':Q1, 'q2':Q2, 'q3':Q3}
-A = NFA(['0','1'], ['q1','q2','q3'], delta)
-print A.to_DFA()
+#Q0 = {'0': ['q1','q2']}
+#Q1 = {'1': ['q1','q2','q3']}
+#Q2 = {'1': ['q1','q2','q3']}
+#Q3 = {}
+#delta = {'q0':Q0, 'q1':Q1, 'q2':Q2, 'q3':Q3}
+#A = NFA(['0','1'], ['q1','q2','q3'], delta)
+#A1 = A.to_DFA()
+#A1 = A1.to_pygraphviz()
+#A1.layout(prog='dot')
+#A1.draw('zzzzzz.png')
                     delta[gnode][i] = states_union #if states_union else {}
         return NFA(alphabet, self.__NFA_final_states(), delta) 
 
+    def to_DFA(self):
+        return self.to_NFA().to_DFA()
 
 #Q0 = {'0':['q1','q2']}
 #Q1 = {'1':['q1'], 'E':['q2']}
 #Q2 = {'1':['q2','q3'], 'E':['q1']}
 #Q3 = {}
 #A = NFAE(['0', '1', 'E'], ['q3'], {'q0':Q0, 'q1':Q1, 'q2':Q2, 'q3':Q3})
-#print A.to_NFA().delta
+#print A.to_NFA()
+#print A.to_DFA()
 #print A.e_closes
 #print A.e_close('q0')
 #print A.e_close('q1')