Subversion Repositories programming

#!/usr/bin/env python
# Copyright: Ira W. Snyder
# Start Date: 2005-10-08
# End Date:
# License: Public Domain
#
# Changelog Follows:
# - 2005-10-16
# - Implemented the nfa class. It's mostly complete at this point.
# - E() function works for circular loops now.
# - 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.
#

################################################################################
# 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
        self.possible_letters = []
        self.dfa_table = []

    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():
                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"""

        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()

            # 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)
                next_st = int(next_st)

                # 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:
                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()

        # 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
        print
        print 'Initial State: %s' % (0, )
        print
        print ' Final     #   NFA  let1  let2'
        print '------------------------------'

        self.__generate_dfa_table()
        for i in self.dfa_table:
            tempstr = ''
            for j in i:
                tempstr = '%s%6s' % (tempstr, j)

            print tempstr

    def __next_states(self, state, letter):
        """Return the next states for the key (state, letter)"""

        try:
            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)] = []

        if letter == '^' and state not in next:
            next.append(state)

        return next

    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:
            storage = []

        # Work around weird mutable default argument stuff
        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, 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, 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 = []

        for i in li:
            if i not in 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)

        self.possible_letters = possible_letters

        #prime the dfa table
        self.make_basic_record(self.__E(0))

        while self.find_unresolved_letter() != (-1, -1): #loop until we've resolved everything
            (record, letter_pos) = self.find_unresolved_letter()
            self.resolve_letter(record, letter_pos)

    def resolve_letter(self, record, letter_pos):
        fromstates = self.dfa_table[record][2]
        tostates = []

        for s in fromstates:
            tostates.extend(self.__next_states(s, self.possible_letters[letter_pos-3]))

        self.dfa_table[record][letter_pos] = self.make_basic_record(tostates)

    def find_unresolved_letter(self): # WORKING
        """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)):
                if self.dfa_table[i][j+3] == None:
                    return (i, j+3)

        return (-1, -1)

    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))
            recordnum = len(self.dfa_table)

            temp_record[1] = recordnum
            temp_record[2] = self.__unique_sort(from_states)
            temp_record[0] = self.__is_list_final(from_states)

            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)


    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.
        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]

        return -1

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