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

 # - Made the nfa.__next_states() function always return a valid reference
 #   to a list in the dictionary. This means you should NEVER use
 #   self.trans_func[(state, letter)] in code anywhere now :)
 # - Final states are now checked for validity.
+#
+# - 2005-10-19
+# - Everything now works, with a menu even.
+#
+# - 2005-10-20
+# - Added the check for <Python-2.3 compatibility.
+# - Commented the source more.
+#
 ################################################################################
 # IMPORTANT NOTES
 ################################################################################
+# The DFA table format:
+#
+# [ [Final, 0, NFA_Equivalent, letter1, letter2, ..., lettern],
+# [ [Final, 1, NFA_Equivalent, letter1, letter2, ..., lettern],
+# [ [Final, 2, NFA_Equivalent, letter1, letter2, ..., lettern] ]
+#
+################################################################################
+# The nfa.trans_func format:
+#
+# dict[(state, letter)] = [list, of, states]
+#
 ################################################################################
+# Check for <Python-2.3 compatibility (boolean values)
+try:
+  True, False
+except NameError:
+  (True, False) = (1, 0)
 import sys, string
 class nfa:
     """Implements a Non-Deterministic Finite Automaton"""
     def __init__(self):
+        """Constructor for the nfa object"""
         self.__clear()
     def __clear(self):
+        """Clear all instance variables of the nfa class"""
         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"""
+        # Check to make sure this can be converted to an int.
+        # Return False if the conversion fails.
         try:
             temp = int(state)
         except (TypeError, ValueError):
             return False
+        # Make sure this is a state in the range
         if temp >= 0 and temp < self.num_states:
             return True
+        # We weren't in the correct range, so return False
         return False
     def __input_num_states(self):
-        """Get the number of states this automaton will have"""
+        """Ask the user (nicely) for the number of states this automaton will have"""
         done = False
         while not done:
             num_states = raw_input('How many states in this automaton: ')
             print
+            # Make sure we can convert the value successfully, then set
+            # the num_states variable.
             try:
                 self.num_states = int(num_states)
                 done = True
             except (TypeError, ValueError):
                 print 'Bad input, not an integer, try again'
                 print
     def __input_final_states(self):
-        """Get final states for this automaton"""
+        """Ask the user for a list of final states for this automaton"""
         print 'Enter final states on one line, seperated by spaces'
         done = False
         while not done:
             final_states = raw_input('Final states: ')
             print
+            # Check each value entered, one by one, and set bad_data if there
+            # was a state out of the valid range
             bad_data = False
             for i in final_states.split():
                 if not self.__state_in_range(i):
                     print 'State %s out of range. All input discarded.' % (i, )
                     print 'Try again please'
                     print
                     bad_data = True
                     break
-            # if we left the for loop with bad data
+            # If we left the for loop with bad data, start over.
             if bad_data:
                 continue
-            # all data is good
+            # All data is good, read the values into the final_states list.
             for i in final_states.split():
                 if self.__state_in_range(i):
                     self.final_states.append(int(i))
             done = True
     def __input_all_edges(self):
-        """Read all of the edges for this automaton"""
+        """Ask the user to input all of the edges for this automaton"""
         print 'Edges take the form "from HERE, by LETTER, to THERE"'
-        print 'Enter something like: "1 a 1" to represent the following'
+        print 'Enter something like: "1 a 3" to represent the following'
-        print 'from q1, by a, go to q1'
+        print 'from q1, by a, go to q3'
         print
-        print 'Conditions:'
+        print 'RULES:'
+        print '------------------------------------------------------'
-        print '1. Blank line to end'
+        print '1. Enter a blank line to stop reading edges'
         print '2. ^ is the empty string'
+        print '3. Enter one letter at a time (no multi-letter states)'
         print
+        # Read edges, one by one. Check them as they are entered.
         done = False
         while not done:
             edge = raw_input('Edge: ')
+            # Check to see if we got a blank line
             if len(edge) == 0:
                 done = True
                 continue
+            # If we didn't get exactly 3 arguments, try again
             if len(edge.split()) != 3:
-                print 'Bad edge entered'
+                print 'Bad edge entered.'
+                print 'Exactly 3 arguments are required for a valid edge.'
                 print
                 continue
+            # All checks appear fine, set a variable for each piece
             (cur_st, letter, next_st) = edge.split()
             # Make sure the states entered are in range
             if self.__state_in_range(cur_st) and self.__state_in_range(next_st):
                 new_state = False
-                cur_st = int(cur_st)
+                cur_st = int(cur_st)    # convert to int
-                next_st = int(next_st)
+                next_st = int(next_st)  # convert to int
                 # Add the state to the list if it's not there already
                 if next_st not in self.__next_states(cur_st, letter):
                     self.__next_states(cur_st, letter).append(next_st)
-            else:
+            else: # At least one state was not in range
                 print 'Invalid current or next state entered'
                 print
                 continue
     def __input_automaton(self):
         self.__input_num_states()
         self.__input_final_states()
         self.__input_all_edges()
-        # Make sure to visit all '^' states (to make printing easier, later)
+        # Make sure to visit all '^' states (to make printing easier)
+        # TODO: See if you need this anymore (I don't think so)
-        for i in range(self.num_states):
+        #for i in range(self.num_states):
-            self.__E(i)
+        #    self.__E(i)
     def main_menu(self):
+        """Display the main menu for this automaton"""
         done = False
         automaton_entered = False
         while not done:
             print 'Menu:'
             else:
                 print 'Bad Selection'
                 print
     def __output_dfa(self):
+        """Generate and print the DFA that corresponds to the NFA entered"""
         print
         print 'Initial State: %s' % (0, )
         print
         self.__generate_dfa_table()
         self.__print_dfa_table()
         print
     def __print_dfa_table(self):
+        """Print out a nicely spaced representation of the DFA's table"""
         #header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv')
         header1 = '%-8s%-8s' % ('Final', 'State #')
         header2 = ''
         for l in self.possible_letters:
             next = self.trans_func[(state, letter)]
         except KeyError:
             # Create a new empty list for this state if it doesn't exist yet
             next = self.trans_func[(state, letter)] = []
+        # Make sure that we can go to ourselves by the empty letter
         if letter == '^' and state not in next:
             next.append(state)
         return next
                         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,
+        """Returns a list of states to where you can go from a group (list)
-        by a certain letter"""
+        of states, with a certain letter"""
         from_states = []
+        # Make sure E() has been called on every state here.
+        # It should have been already, but just to make sure,
+        # we'll do it here, too :)
         for s in states:
             from_states.extend(self.__E(s))
         from_states = self.__unique_sort(from_states)
         new_states = []
+        # For each state, find the next states, and add them to the list
         for s in from_states:
             new_states.extend(self.__next_states(s, letter))
         new_states = self.__unique_sort(new_states)
                 return True
         return False
     def __get_temp_record(self, num_letters):
+        """Create a record (for the DFA table) that has the proper number
+        of slots"""
         blank = None
         return [blank for i in range(num_letters + 3)]
     def __get_possible_letters(self):
+        """Create a list of all the possible letters for the NFA,
+        and store it in possible_letters"""
-        # get the list of all letters
+        # Get the list of all letters
         possible_letters = []
         for (state, letter) in self.trans_func.keys():
             if letter not in possible_letters and letter != '^':
                 possible_letters.append(letter)
         possible_letters = self.__unique_sort(possible_letters)
         self.possible_letters = possible_letters
     def __generate_dfa_table(self):
+        """Generate a table for the DFA representation of the NFA entered earlier"""
-        # get all the possible letters
+        # Get all the possible letters
         self.__get_possible_letters()
-        # prime the dfa table
+        # Prime the dfa table with the first state
         self.make_basic_record(self.__E(0))
+        # Loop until we resolve every letter in the table
-        while self.find_unresolved_letter() != (-1, -1): #loop until we've resolved everything
+        while self.find_unresolved_letter() != (-1, -1):
             (record, letter_pos) = self.find_unresolved_letter()
             self.resolve_letter(record, letter_pos)
     def resolve_letter(self, record, letter_pos):
+        """Resolve a letter in the table, either adding a new entry if the
+        required state doesn't already exist, or putting a link to
+        an existing state"""
+        # Get the NFA equivalent multi-state
         fromstates = self.dfa_table[record][2]
         tostates = []
+        # Find all the states we can go to from our multi-state
         for s in fromstates:
             tostates.extend(self.__next_states(s, self.possible_letters[letter_pos-3]))
+        tostates = self.__unique_sort(tostates)
+        # Make the letter we are trying to resolve point to a record in the table.
+        # make_basic_record() will return the correct record, even if it needs to
+        # create a new one.
         self.dfa_table[record][letter_pos] = self.make_basic_record(tostates)
-    def find_unresolved_letter(self): # WORKING
+    def find_unresolved_letter(self):
         """Returns an index pair of an unresolved letter that exists in the dfa_table.
         If there are no more letters, return (-1, -1)"""
         for i in range(len(self.dfa_table)):
             for j in range(len(self.possible_letters)):
                     return (i, j+3)
         return (-1, -1)
     def make_basic_record(self, from_states):
+        """Create a record, if necessary, for the states "from_states."
+        If a corresponding state already exists, return it's index. A new state
+        will have everything but the letters filled in."""
         if self.dfa_state_exists(from_states) == -1: #doesn't exist
             temp_record = self.__get_temp_record(len(self.possible_letters))
             recordnum = len(self.dfa_table)

Subversion Repositories programming

(root)/school/cs311/proj2/proj2.py – Rev 138 → 140