Subversion Repositories programming

#!/usr/bin/env python
# Copyright: Ira W. Snyder
# Start Date: 2005-10-08
# End Date: 
# License: Public Domain
#
# Changelog Follows:
#

################################################################################
# IMPORTANT NOTES
################################################################################
################################################################################

import sys, string

class nfa:
    """Implements a Non-Deterministic Finite Automaton"""

    def __init__(self):
        self.trans_func = {}
        self.num_states = 0
        self.final_states = []
        self.initial_state = 0
        
    def __state_in_range(self, state):
        """Check if a given state is in the acceptable range"""

        try:
            temp = int(state)
        except (TypeError, ValueError):
            return False

        if temp >= 0 and temp < self.num_states:
            return True

        return False
            
    def __input_num_states(self):
        """Get the number of states this automaton will have"""

        done = False
        while not done:
            num_states = raw_input('How many states in this automaton: ')

            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"""

        print 'Enter final states on one line, seperated by spaces'
        
        done = False
        while not done:
            final_states = raw_input('Final states: ')
            
            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 bad_data:
                continue

            # all data is good
            for i in final_states.split():
                self.final_states.append(int(i))

            done = True

    def __input_all_edges(self):
        """Read 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 'from q1, by a, go to q1'
        print
        print 'Conditions:'
        print '1. Blank line to end'
        print '2. ^ is the empty string'

        done = False
        while not done:
            edge = raw_input('Edge: ')

            if len(edge) == 0:
                done = True
                continue
            
            if len(edge.split()) != 3:
                print 'Bad edge entered'
                print
                continue
                
            (cur_st, letter, next_st) = edge.split()

            if self.__state_in_range(cur_st) and self.__state_in_range(next_st):
                new_state = False

                try:
                    self.trans_func[(int(cur_st), letter)]
                except KeyError:
                    new_state = True

                if new_state:
                    self.trans_func[(int(cur_st), letter)] = [int(next_st)]
                else:
                    self.trans_func[(int(cur_st), letter)].append(int(next_st))

            else:
                print 'Invalid current or next state entered'
                print
                continue
                
    def __input_automaton(self):
        """Read this entire automaton's input"""

        self.__input_num_states()
        self.__input_final_states()
        self.__input_all_edges()

    def main_menu(self):
        self.__input_automaton()

        print self.trans_func
        print self.num_states
        print self.final_states
        print self.initial_state
        print 'E(0): %s' % (self.__E(0), )
        print 'E(1): %s' % (self.__E(1), )

    def __next_states(self, state, letter):
        next = []
        
        try:
            next = self.trans_func[(state, letter)]
        except KeyError:
            pass

        return next
        
    def __E(self, state, storage=[], visited=[]):
        
        # If nothing was inputted for the null string from this state
        # return itself only (as a list)
        if len(self.__next_states(state, '^')) == 0:
            print 'stop rec: %s' % ([state], )
            return [state]
        
        for i in self.__next_states(state, '^'):
            print 'next state: %s -- storage: %s -- visited: %s' % (i, storage, visited)

            if i not in storage and i not in visited:
                storage.append(state) #add yourself to the list
                visited.append(i)
                print 'making the call: (%s, %s, %s)' % (i, storage, visited)
                storage.extend(self.__E(i, storage, visited))

        return storage
        
    def output_dfa(self):
        #stuff here
        pass

if __name__ == '__main__':
    automaton = nfa()
    automaton.main_menu()