WebSVN – programming – Diff – /school/cs311/proj2/proj2.py

     def __init__(self):
         self.trans_func = {}
         self.num_states = 0
         self.final_states = []
         self.initial_state = 0
+        self.possible_letters = []
+        self.dfa_table = []
     def __state_in_range(self, state):
         """Check if a given state is in the acceptable range"""
         try:
         self.__input_num_states()
         self.__input_final_states()
         self.__input_all_edges()
+        # Make sure to visit all '^' states (to make printing easier, later)
+        for i in range(self.num_states):
+            self.__E(i)
     def main_menu(self):
         #NOTE: All of this code is not what it's supposed to be.
         #      It is for TESTING ONLY.
+        #
         #TODO: Generate a menu :)
         self.__input_automaton()
-        print self.trans_func
-        print self.num_states
-        print self.final_states
-        print self.initial_state
         print
+        print
+        print 'Initial State: %s' % (0, )
+        print
+        print ' Final     #   NFA  let1  let2'
+        print '------------------------------'
+        self.__generate_dfa_table()
-        for i in range(self.num_states):
+        for i in self.dfa_table:
+            tempstr = ''
+            for j in i:
-            print 'E(%d): %s' % (i, self.__E(i))
+                tempstr = '%s%6s' % (tempstr, j)
+            print tempstr
     def __next_states(self, state, letter):
         """Return the next states for the key (state, letter)"""
         try:
         if letter == '^' and state not in next:
             next.append(state)
         return next
-    def __E(self, state, storage=None, visited=None):
+    def __E(self, state, letter='^', storage=None, visited=None):
         """Calculate E(state) and return it. This handles circular E()
         calculations."""
         # Work around weird mutable default argument stuff
         if storage is None:
         if visited is None:
             visited = []
         # Find all of the direct next states that we can get to by
         # the empty string, and append anything that is not already there
-        for i in self.__next_states(state, '^'):
+        for i in self.__next_states(state, letter):
             if i not in storage:
                 storage.append(i)
         # Visit everything in storage that has not been visited already
         for i in storage:
             if i not in visited:
                 visited.append(i)
-                temp = self.__E(i, storage, visited)
+                temp = self.__E(i, letter, storage, visited)
                 # Avoid duplicating things in storage
                 for j in temp:
                     if j not in storage:
                         storage.append(j)
         return storage
+    def __by_letter(self, states, letter):
+        """Returns a list of states to where you can go from a list of states,
+        by a certain letter"""
+        from_states = []
+        for s in states:
+            from_states.extend(self.__E(s))
+        from_states = self.__unique_sort(from_states)
+        new_states = []
+        for s in from_states:
+            new_states.extend(self.__next_states(s, letter))
+        new_states = self.__unique_sort(new_states)
+        return new_states
     def __unique_sort(self, li):
         """Make sure everything in a list is unique, and then sort it"""
         newlist = []
                 newlist.append(i)
         newlist.sort()
         return newlist
+    def __is_final_state(self, state):
+        """Check if a state is a final state."""
+        if state in self.final_states:
+            return True
+        return False
+    def __is_list_final(self, states):
+        """Check if at least one state in the list "states" is final"""
+        for s in states:
+            if self.__is_final_state(s):
+                return True
+        return False
+    def __get_temp_record(self, num_letters):
+        blank = None
+        return [blank for i in range(num_letters + 3)]
     def __generate_dfa_table(self):
         # get the list of all letters
         possible_letters = []
         for (state, letter) in self.trans_func.keys():
             if letter not in possible_letters:
                 possible_letters.append(letter)
-        # DFA_TABLE STRUCTURE
-        #
-        # [ [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n]
-        #   [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n]
+        self.possible_letters = possible_letters
-        #   [Final, DFA_State_Number, [States_in_NFA], letter_1, letter_2, ..., letter_n] ]
-        #
-        dfa_table = []
+        #prime the dfa table
+        self.make_basic_record(self.__E(0))
-        # find the first state's definition
+        while self.find_unresolved_letter() != (-1, -1): #loop until we've resolved everything
-        def_in_nfa = self.__E(0)
+            (record, letter_pos) = self.find_unresolved_letter()
-        is_final = False
+            self.resolve_letter(record, letter_pos)
+    def resolve_letter(self, record, letter_pos):
+        fromstates = self.dfa_table[record][2]
-        temp_record = []
+        tostates = []
-        # find out if we're final
-        for i in def_in_nfa:
+        for s in fromstates:
-            if i in self.final_states:
+            tostates.extend(self.__next_states(s, self.possible_letters[letter_pos-3]))
-                is_final = True
-                break
-        temp_record.append(is_final)
-        temp_record.append(len(dfa_table))
+        self.dfa_table[record][letter_pos] = self.make_basic_record(tostates)
-        temp_record.append(def_in_nfa)
-        # find out where we can go by each letter
+    def find_unresolved_letter(self): # WORKING
-        for l in possible_letters:
+        """Returns an index pair of an unresolved letter that exists in the dfa_table.
-            where_to_go = []
+        If there are no more letters, return (-1, -1)"""
-            for s in def_in_nfa:
+        for i in range(len(self.dfa_table)):
-                where_to_go.extend(self.__next_states(s, l))
+            for j in range(len(self.possible_letters)):
+                if self.dfa_table[i][j+3] == None:
+                    return (i, j+3)
-            where_to_go = self.__unique_sort(where_to_go)
+        return (-1, -1)
-            create_new_state = True
+    def make_basic_record(self, from_states):
+        if self.dfa_state_exists(from_states) == -1: #doesn't exist
+            temp_record = self.__get_temp_record(len(self.possible_letters))
-            for s in dfa_table:
+            recordnum = len(self.dfa_table)
-                if s[2] == where_to_go:
+            temp_record[1] = recordnum
-                    temp_record.append(s[1])
+            temp_record[2] = self.__unique_sort(from_states)
-                    create_new_state = False
+            temp_record[0] = self.__is_list_final(from_states)
-                    break
+            self.dfa_table.append(temp_record)
+        # always return a re-call of the function. This will not fail, since a new
+        # record is added above if a record does not already exist.
+        return self.dfa_state_exists(from_states)
-            if create_new_state:
-                # recurse???
-                pass
-################################################################################
-# NEW STUFF IS AFTER THIS
-################################################################################
-        temp_record = [None for n in range(len(possible_letters) + 3)]
-        # start at initial state
-        # generate E(initial_state)
-        # find out if we are a final state (based on E() )
-        # name the state (starting at 0)
-        #
-    def output_dfa(self):
+    def dfa_state_exists(self, from_states):
+        """Find out if this state already exists in the dfa table.
+        If it does exist, return it's dfa state name.
-        #stuff here
+        If it does not exist, return -1"""
+        sorted_states = self.__unique_sort(from_states)
+        for i in range(len(self.dfa_table)):
+            if self.dfa_table[i][2] == sorted_states:
+                return self.dfa_table[i][1]
-        pass
+        return -1
 if __name__ == '__main__':
     automaton = nfa()
     automaton.main_menu()

Subversion Repositories programming

(root)/school/cs311/proj2/proj2.py – Rev 135 → 136